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 13 phút

Bên trong bộ định tuyến: cổng đầu vào, mạng chuyển mạch, cổng đầu ra và hàng đợi

Một bộ định tuyến trông như một chiếc hộp, nhưng bên trong là một nhà máy nhỏ với bốn phòng ban. Biết mỗi phòng làm gì, và gói tin dồn lại ở đâu giữa chúng, sẽ giải thích phần lớn độ trễ và mất gói trên Internet.

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 4 · Kiến trúc bộ định tuyến
Biên soạn từ

Kurose và Ross, Computer Networking: A Top-Down Approach, mục 4.2, đối chiếu với RFC 1812 (Requirements for IP Version 4 Routers) và RFC 7567 (IETF Recommendations Regarding Active Queue Management). Mọi con số đều được tính lại bằng mã.

Cách sử dụng

Hãy vẽ bộ định tuyến từ trí nhớ: đầu vào bên trái, mạng chuyển mạch ở giữa, đầu ra bên phải, bộ xử lý định tuyến ở trên. Rồi đánh dấu hai chỗ một gói tin có thể phải chờ: trước mạng chuyển mạch và sau nó.

Ghi chú về nguồn

Các slide giáo trình thường viết head-of-the-line (HOL) blocking; hầu hết tài liệu khác viết head-of-line blocking. Là một. Drop-tail và tail drop cũng là một chính sách với hai cách viết.

Hình dung: hệ thống hành lý ở sân bay#

Hãy nghĩ về chiếc vali của bạn ở sân bay. Bạn đưa nó ở quầy làm thủ tục. Nhân viên đọc xem bạn bay đến đâu và gắn thẻ. Hành lý rơi xuống các băng chuyền dưới sàn, đưa nó tới khu bốc xếp của cổng bạn. Ở đó nó chờ cùng các hành lý khác cho đến khi được xếp lên máy bay.

Ở tầng trên, một phòng điều khiển quyết định mỗi chuyến bay dùng cổng nào và in các bảng mà nhân viên quầy đọc.

Một bộ định tuyến được xây theo cách tương tự. Các quầy là cổng đầu vào. Các băng chuyền là mạng chuyển mạch. Các khu bốc xếp là cổng đầu ra. Phòng điều khiển là bộ xử lý định tuyến. Và nếu ba quầy gửi hành lý tới một cổng nhanh hơn mức nó bốc xếp được, đống hành lý lớn dần. Khi khu bốc xếp đầy, hành lý mới bị bỏ lại. Trên mạng, đó là một gói tin bị mất.

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

Thuật ngữÝ nghĩa
Cổng đầu vàoNơi một liên kết đi vào bộ định tuyến. Nó nhận các bit, mở khung, tra cứu đích và chuyển datagram cho mạng chuyển mạch.
Cổng đầu raNơi một liên kết rời bộ định tuyến. Nó giữ các datagram đang chờ và gửi chúng lên liên kết đi ra.
Mạng chuyển mạch (switching fabric)Các kết nối bên trong bộ định tuyến mang một datagram từ cổng đầu vào tới cổng đầu ra.
Bộ xử lý định tuyếnMáy tính thông thường của bộ định tuyến. Nó chạy mặt phẳng điều khiển và xây dựng bảng chuyển tiếp.
Tốc độ đường truyền (R)Một liên kết mang bit nhanh đến mức nào, ví dụ 10 Gbps (mười tỷ bit mỗi giây).
Tiền tốNhững bit đầu tiên của một địa chỉ, dùng chung cho cả một khối. Trong 198.51.100.128/26, /26 nghĩa là “26 bit đầu tiên”.
Bộ đệm (buffer)Bộ nhớ nơi các gói tin chờ trong một hàng đợi (queue).
HOL blockingHead-of-line blocking: gói tin ở đầu một hàng đợi đầu vào bị kẹt, nên các gói tin phía sau cũng phải chờ, dù đầu ra của chúng đang rảnh.
Drop-tailQuy tắc đơn giản nhất cho bộ đệm đầy: vứt bỏ gói tin vừa mới đến.

Bốn bộ phận và hai mặt phẳng#

Mọi bộ định tuyến đều có cùng bốn bộ phận. Ba trong số đó xử lý mọi gói tin. Bộ phận thứ tư hoàn toàn không chuyển tiếp gói tin.

PhầnTác dụngMặt phẳng
Cổng đầu vàoNhận, mở gói, tra cứu, xếp hàngDữ liệu (phần cứng)
Mạng chuyển mạch (switching fabric)Đưa mỗi datagram tới đúng đầu raDữ liệu (phần cứng)
Cổng đầu raXếp hàng, đóng vào khung mới, gửiDữ liệu (phần cứng)
Bộ xử lý định tuyếnChạy các giao thức định tuyến, xây dựng bảng chuyển tiếpĐiều khiển (phần mềm)

Vì sao dùng phần cứng? Một gói tin cỡ đầy đủ 1.500 byte là 12.000 bit. Trên một liên kết 10 Gbps nó đến trong 12.000 ÷ 10.000.000.000 = 1,2 micro giây. Vì vậy mỗi lần tra cứu phải xong trong khoảng một micro giây, trên mọi cổng cùng lúc. Với các gói tin cỡ tối thiểu 64 byte, nó là 512 ÷ 10.000.000.000 = 51,2 nano giây, đó là lý do chuyển tiếp được mô tả là mất vài nano giây. Phần mềm không theo kịp tốc độ đó. Để hỗ trợ, bộ xử lý sao chép bảng chuyển tiếp tới mọi cổng đầu vào, và mỗi cổng tra cứu từ bản sao của riêng nó.

Cổng đầu vào và bảng chuyển tiếp#

Một cổng đầu vào làm bốn việc, theo thứ tự:

  1. Kết thúc đường truyền (line termination): biến tín hiệu trên dây hoặc sợi quang trở lại thành các bit (tầng vật lý).
  2. Xử lý tầng liên kết: kiểm tra khung và mở datagram bên trong.
  3. Tra cứu: đọc địa chỉ IP đích và tìm cổng đầu ra.
  4. Xếp hàng: nếu mạng chuyển mạch đang bận, giữ datagram cho đến khi nó có thể đi qua.

Trong chuyển tiếp theo địa chỉ đích, địa chỉ đích là trường duy nhất có ý nghĩa. Một hàng cho mỗi địa chỉ sẽ cần khoảng 4 tỷ hàng, nên bảng liệt kê các dải thay vào đó.

Dải địa chỉ đíchLiên kết đầu ra
198.51.100.0 đến 198.51.100.1270
198.51.100.128 đến 198.51.100.1911
198.51.100.192 đến 198.51.100.2552
Mọi trường hợp khác3

Mỗi dải là một khối chung một tiền tố. Viết byte cuối ở dạng nhị phân là thấy. Trong dải đầu tiên, byte cuối luôn bắt đầu bằng 0: đó là 24 bit của 198.51.100 cộng thêm một bit, viết là 198.51.100.0/25 (128 địa chỉ). Dải thứ hai bắt đầu bằng 10: 198.51.100.128/26 (64 địa chỉ). Dải thứ ba bắt đầu bằng 11: 198.51.100.192/26 (64 địa chỉ). Ba tiền tố thay thế 256 hàng.

Ví dụ có lời giải

Một datagram đến cho 198.51.100.150. Byte cuối, 150, là 10010110. Nó bắt đầu bằng 10, nên khớp với 198.51.100.128/26: liên kết 1. Với 198.51.100.37 byte cuối là 00100101, bắt đầu bằng 0: liên kết 0. 203.0.113.9 không khớp tiền tố nào, nên dùng hàng cuối: liên kết 3.

Giờ thêm một hàng 198.51.100.160/27 → liên kết 4. Nó bao phủ 198.51.100.160 đến 198.51.100.191, nằm trong dải của liên kết 1, nên 198.51.100.170 khớp hai hàng. Quy tắc là khớp tiền tố dài nhất: dùng tiền tố dài nhất, cụ thể nhất. /27 thắng /26, nên nó đi tới liên kết 4. Bài hướng dẫn khớp tiền tố dài nhất trình bày đầy đủ quy tắc này. Bộ định tuyến thực hiện tra cứu trong loại bộ nhớ đặc biệt gọi là TCAM (ternary content-addressable memory), kiểm tra mọi hàng cùng một lúc.

Ba cách xây dựng mạng chuyển mạch#

Khi cổng đã biết đầu ra, datagram phải đi qua bộ định tuyến. Có ba thiết kế cổ điển.

Chuyển mạch qua bộ nhớ

Bộ định tuyến thực chất là một máy tính. Datagram được sao chép vào bộ nhớ, bộ xử lý tìm đầu ra, và datagram được sao chép ra lại. Vì vậy nó đi qua bus bộ nhớ hai lần. Nếu bus bộ nhớ chuyển 20 Gbps, bộ định tuyến chuyển tiếp tối đa 20 ÷ 2 = 10 Gbps.

Chuyển mạch qua bus

Đầu vào đặt datagram thẳng lên một bus dùng chung (dây mà mọi cổng đều thấy), gắn nhãn đầu ra của nó. Mọi đầu ra đều thấy nó; chỉ đầu ra được gắn nhãn giữ lại. Không có bản sao thứ hai, nhưng mỗi lúc bus chỉ chứa được một datagram. Vì vậy bộ định tuyến không bao giờ chuyển tiếp nhanh hơn bus.

Chuyển mạch qua mạng kết nối (crossbar)

Một crossbar có một bus ngang từ mỗi trong N đầu vào và một bus dọc tới mỗi trong N đầu ra: 2N bus. Ở chỗ hai bus giao nhau, một công tắc có thể đóng. Một crossbar 8 cổng có 16 bus và 8 × 8 = 64 điểm giao. Các datagram đi qua cùng lúc nếu chúng đến các đầu ra khác nhau. Hai datagram cho cùng một đầu ra phải lần lượt thay phiên.

Mạng chuyển mạchSố datagram cùng lúcGiới hạn tốc độ
Bộ nhớMộtMột nửa băng thông bus bộ nhớ
BusMộtBăng thông của bus
CrossbarTối đa NChỉ phải chờ khi hai datagram muốn cùng một đầu ra

Nếu mạng chuyển mạch chạy với tốc độ gấp N lần tốc độ đường truyền (N × R), các đầu vào không bao giờ phải chờ nó. Với 8 cổng ở 10 Gbps, đó là 80 Gbps.

Đừng nhầm lẫn các khái niệm này
Bus là một đường dùng chung; crossbar là nhiều đường. Bus mang một datagram mỗi lúc. Crossbar mang nhiều datagram cùng lúc, miễn là các đầu ra của chúng khác nhau.

Gói tin chờ ở đâu, và bị mất ở đâu#

Gói tin chờ ở hai nơi: ở cổng đầu vào, trước mạng chuyển mạch, và ở cổng đầu ra, sau nó. Nếu một trong hai bộ đệm đầy, gói tin bị mất.

Xếp hàng đầu vào và head-of-line blocking

Hàng đợi đầu vào dài ra khi mạng chuyển mạch không thể mang mọi thứ cùng lúc, ví dụ khi hai đầu vào muốn cùng một đầu ra. Một bên thắng và một bên chờ. Hàng đợi là vào trước ra trước, nên mọi thứ phía sau bên thua cũng phải chờ.

Ví dụ có lời giải

Một crossbar có các đầu ra X, Y và Z. Gói tin đầu hàng của đầu vào 1 dành cho X. Gói tin đầu hàng của đầu vào 2 cũng dành cho X, với một gói tin cho Y ở phía sau. Y đang rảnh. Đầu vào 1 thắng, nên gói tin của nó đi qua. Gói tin đầu hàng của đầu vào 2 chờ X, và gói tin cho Y chờ phía sau nó, dù Y đang rảnh. Đó là HOL blocking. Với lưu lượng ngẫu nhiên, nó có thể giới hạn một bộ chuyển mạch xếp hàng ở đầu vào ở mức khoảng 58% công suất.

Xếp hàng đầu ra và mất gói

Ngay cả với mạng chuyển mạch nhanh, gói tin vẫn dồn lại ở một đầu ra khi nhiều đầu vào cùng gửi tới nó. Chúng đến nhanh hơn một liên kết có thể gửi đi.

Ví dụ có lời giải

Ba đầu vào mỗi cái gửi tới một đầu ra với tốc độ đầy đủ 10 Gbps. Gói tin đến ở 30 Gbps và đi ra ở 10 Gbps, nên hàng đợi tăng với tốc độ 20 Gbps. Bộ đệm chứa 1.000 gói tin 1.500 byte: 1.000 × 1.500 × 8 = 12.000.000 bit. Nó đầy sau 12.000.000 ÷ 20.000.000.000 giây = 0,6 mili giây.

Với drop-tail, bộ đệm đầy sẽ loại bỏ từng gói đến mới. Một số bộ định tuyến dùng quản lý hàng đợi chủ động (active queue management) thay vào đó: chúng loại bỏ gói tin, hoặc đặt cờ tắc nghẽn trong chúng, một chút trước khi bộ đệm đầy, để cảnh báo bên gửi sớm. RFC 7567 khuyến nghị điều này, nhưng hãy giả định drop-tail trừ khi câu hỏi nói khác.

Đừng nhầm lẫn các khái niệm này
HOL blocking chỉ xảy ra ở hàng đợi đầu vào. Gói tin bị chặn có đầu ra rảnh nhưng không thể tới mạng chuyển mạch. Ở hàng đợi đầu ra, gói tin chờ vì liên kết của chính chúng đang bận. Mạng chuyển mạch nhanh hơn loại bỏ được xếp hàng đầu vào. Không có gì bên trong bộ định tuyến loại bỏ được xếp hàng đầu ra.

Bộ đệm nên lớn đến mức nào?

Quá nhỏ, các đợt bùng phát ngắn gây mất gói. Quá lớn, gói tin chờ lâu đến mức độ trễ trở thành vấn đề (bufferbloat). Quy tắc kinh nghiệm cổ điển dùng thời gian khứ hồi (RTT) trung bình và dung lượng liên kết C để đặt kích thước bộ đệm B:

B = RTT × C

Nghiên cứu năm 2004 (Appenzeller, Keslassy và McKeown) cho thấy với N luồng TCP độc lập (các kết nối riêng biệt chia sẻ liên kết), ít hơn nhiều là đủ:

B = RTT × C ÷ √N

Ví dụ có lời giải

Một liên kết 10 Gbps, RTT 250 mili giây. Quy tắc kinh nghiệm: 0,25 × 10.000.000.000 = 2.500.000.000 bit = 312,5 megabyte. Với 10.000 luồng, √10.000 = 100, nên 2.500.000.000 ÷ 100 = 25.000.000 bit = 3,125 megabyte. Ít hơn một trăm lần.

Các nhà sản xuất thực tế định cỡ bộ đệm theo nhiều cách. Cả hai công thức đều chỉ là hướng dẫn, không phải định luật.

Lập lịch gói tin: ai đi tiếp theo#

Khi gói tin chờ ở một đầu ra, bộ lập lịch (scheduler) chọn gói tiếp theo để gửi.

Cơ chếCách chọn
FIFO (vào trước ra trước)Theo thứ tự đến. Mặc định.
Ưu tiênGói tin được xếp vào các lớp. Luôn gửi từ lớp cao nhất đang có gói tin. Một lớp cao đang bận có thể bỏ đói các lớp thấp.
Round robinLần lượt một gói tin từ mỗi lớp, bỏ qua các lớp rỗng.
Weighted fair queuing (WFQ)Round robin có trọng số: lớp i nhận ít nhất wi ÷ (tổng mọi trọng số) của liên kết.
Ví dụ có lời giải

Một liên kết 12 Mbps có ba lớp với trọng số 3, 2 và 1. Các trọng số có tổng là 6. Các lớp nhận 3/6 × 12 = 6 Mbps, 2/6 × 12 = 4 Mbps và 1/6 × 12 = 2 Mbps. Phần của một lớp rỗng được chuyển cho các lớp khác.

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

Một datagram được tra cứu ở cổng đầu vào, nơi nó có thể phải chờ và chịu head-of-line blocking, đi qua mạng chuyển mạch (bộ nhớ, bus hoặc crossbar), và chờ ở cổng đầu ra, nơi một bộ lập lịch chọn gói đi tiếp theo và drop-tail loại bỏ các gói đến khi bộ đệm đã đầy.

Luyện tập#

Hãy vẽ bộ định tuyến trước và đánh dấu gói tin đang ở đâu. Ghi đơn vị trong mọi phép tính.

  1. Hãy nêu tên bốn bộ phận của bộ định tuyến và mặt phẳng mà mỗi bộ phận thuộc về.
  2. Dùng bảng chuyển tiếp ở trên cộng với hàng 198.51.100.160/27 → liên kết 4, mỗi địa chỉ đích dùng liên kết nào? (a) 198.51.100.100 (b) 198.51.100.175 (c) 198.51.100.230 (d) 192.0.2.1
  3. Một bộ định tuyến chuyển mạch qua bộ nhớ, và bus bộ nhớ của nó chuyển 40 Gbps. Tốc độ chuyển tiếp cao nhất của nó là bao nhiêu?
  4. Một crossbar có các đầu ra P, Q và R. Gói tin đầu hàng của đầu vào 1 dành cho P. Gói tin đầu hàng của đầu vào 2 dành cho P, với một gói cho Q ở phía sau. Gói tin đầu hàng của đầu vào 3 dành cho R. Đầu vào 1 thắng. Cái gì đi qua trong lượt này, và đầu ra nào đang rảnh mà đáng lẽ không phải vậy?
  5. Bốn đầu vào và một đầu ra, tất cả 10 Gbps. Cả bốn cùng gửi tới đầu ra đó với tốc độ đầy đủ. Bộ đệm đầu ra chứa 6 megabyte. Bao lâu thì bắt đầu mất gói?
  6. Một liên kết 40 Gbps có RTT 100 mili giây và mang 40.000 luồng TCP. Hãy tính kích thước bộ đệm theo quy tắc kinh nghiệm và theo quy tắc √N, tính bằng megabyte.
  7. Một liên kết 100 Mbps dùng WFQ với trọng số 5, 3 và 2. Mỗi lớp được đảm bảo bao nhiêu?

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. Cổng đầu vào, mạng chuyển mạch và cổng đầu ra: mặt phẳng dữ liệu. Bộ xử lý định tuyến: mặt phẳng điều khiển. Ba bộ phận đầu xử lý mọi gói tin bằng phần cứng; bộ xử lý xây dựng bảng chuyển tiếp.
  2. (a) Liên kết 0. (b) Liên kết 4. (c) Liên kết 2. (d) Liên kết 3. 100 là 01100100, nên là /25. 175 là 10101111: nó khớp với /26 và /27 (160 đến 191), và /27 dài hơn thắng. 230 là 11100110, nên là 198.51.100.192/26. 192.0.2.1 không khớp gì, nên dùng hàng mặc định.
  3. 20 Gbps. Mỗi datagram đi qua bus bộ nhớ hai lần, nên 40 ÷ 2 = 20.
  4. Đầu vào 1 tới P và đầu vào 3 tới R đi qua. Q đang rảnh. Gói tin đầu hàng của đầu vào 2 chờ P, và gói cho Q bị kẹt phía sau nó: HOL blocking.
  5. 1,6 mili giây. Lượng đến 4 × 10 = 40 Gbps, lượng đi 10 Gbps, nên tốc độ tăng là 30 Gbps. 6.000.000 × 8 = 48.000.000 bit. 48.000.000 ÷ 30.000.000.000 = 0,0016 s.
  6. 500 MB và 2,5 MB. 0,1 × 40.000.000.000 = 4.000.000.000 bit = 500 MB. √40.000 = 200, và 4.000.000.000 ÷ 200 = 20.000.000 bit = 2,5 MB.
  7. 50, 30 và 20 Mbps. Các trọng số có tổng là 10: 5/10, 3/10 và 2/10 của 100.

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

  • ☐  Tôi có thể vẽ bốn bộ phận của bộ định tuyến và nói mỗi bộ phận thuộc mặt phẳng nào.
  • ☐  Tôi có thể liệt kê bốn việc của một cổng đầu vào và tra cứu một địa chỉ đích, kể cả khi các tiền tố chồng lấn nhau.
  • ☐  Tôi có thể nêu giới hạn tốc độ của chuyển mạch qua bộ nhớ, qua bus và qua crossbar.
  • ☐  Tôi có thể giải thích head-of-line blocking bằng một ví dụ nhỏ.
  • ☐  Tôi có thể tính hàng đợi đầu ra đầy nhanh đến đâu, và định cỡ bộ đệm bằng RTT × C và RTT × C ÷ √N.
  • ☐  Tôi có thể mô tả FIFO, ưu tiên, round robin và WFQ, và tính các phần của WFQ.
Một quy tắc cuối cùng

Khi một gói tin phải chờ, hãy hỏi ở đâu. Trước mạng chuyển mạch nghĩa là xếp hàng đầu vào, có thể là HOL blocking. Sau nó nghĩa là xếp hàng đầu ra: quá nhiều lưu lượng cho một liên kết đi ra.

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

Các bộ phận chính của một bộ định tuyến là gì?

Các cổng đầu vào, một mạng chuyển mạch (switching fabric) và các cổng đầu ra, hợp thành mặt phẳng dữ liệu, cộng với một bộ xử lý định tuyến, chạy mặt phẳng điều khiển và xây dựng bảng chuyển tiếp.

Head-of-line blocking là gì?

Ở một hàng đợi đầu vào vào trước ra trước, khi gói tin ở đầu hàng phải chờ một đầu ra đang bận, mọi gói tin phía sau nó cũng phải chờ, dù đầu ra của chúng đang rảnh.

Mạng chuyển mạch nào nhanh nhất?

Crossbar hoặc một mạng kết nối khác, vì nó mang nhiều datagram cùng lúc khi các đầu ra của chúng khác nhau.

Vì sao bộ định tuyến loại bỏ gói tin?

Khi các gói tin đến một đầu ra nhanh hơn liên kết của nó có thể gửi đi, bộ đệm đầu ra đầy lên. Khi đó một bộ định tuyến drop-tail loại bỏ từng gói đến mới cho đến khi có chỗ trống.

Đề 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ó 10 câu hỏi về bài hướng dẫn 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 →