Kurose và Ross, Computer Networking: A Top-Down Approach, mục 4.2.1 (chuyển tiếp theo địa chỉ đích) và mục 4.3 (địa chỉ IPv4 và tổng hợp tuyến), đối chiếu với RFC 4632 (Classless Inter-domain Routing). Mọi kết quả khớp và tổng hợp trên trang này đều được tính lại bằng mô-đun ipaddress của Python.
Hãy viết địa chỉ đích ra nhị phân trước, rồi xếp tiền tố của từng mục trong bảng thẳng hàng bên dưới nó. Đừng đoán từ dạng thập phân có dấu chấm: tiền tố hiếm khi kết thúc đúng ở ranh giới byte, và đó chính là chỗ có bẫy.
Bức tranh chung: phân loại thư#
Hãy hình dung một người phân loại thư với hai tấm biển trên tường. Một tấm ghi: “Mọi thư gửi đi Canada cho vào ngăn 1.” Tấm kia ghi: “Mọi thư gửi đi Toronto cho vào ngăn 2.”
Một lá thư gửi đi Toronto khớp với cả hai tấm biển. Rốt cuộc Toronto nằm ở Canada. Người phân loại cho nó vào ngăn 2, vì tấm biển đó cụ thể hơn. Có người đã viết nó đúng cho trường hợp này. Một lá thư gửi đi Ottawa chỉ khớp tấm biển đầu, nên vào ngăn 1.
Bộ định tuyến làm điều tương tự với các địa chỉ. Khi có nhiều hơn một mục trong bảng chuyển tiếp phù hợp với một địa chỉ đích, nó dùng mục cụ thể nhất: mục có tiền tố dài nhất.
Từ vựng, trước khi dùng đến#
| Thuật ngữ | Ý nghĩa |
|---|---|
| Tiền tố | Các bit ngoài cùng bên trái của một địa chỉ mà một mục trong bảng quan tâm, viết là a.b.c.d/x. x là số bit. |
| Bảng chuyển tiếp | Danh sách các mục của bộ định tuyến: “các đích bắt đầu bằng tiền tố này thì đi ra khỏi liên kết kia”. |
| Khớp | Một mục khớp một địa chỉ đích khi x bit đầu của địa chỉ đích bằng x bit tiền tố của mục đó. |
| Khớp tiền tố dài nhất | Khi nhiều mục cùng khớp, dùng mục có x lớn nhất. Còn gọi là longest prefix match. |
| Tuyến mặc định | Mục 0.0.0.0/0. Tiền tố của nó có không bit nào, nên nó khớp mọi thứ, và nó chỉ được dùng khi không có gì dài hơn khớp. |
| Thông báo (advertise) | Để một mạng nói với các mạng khác, qua một giao thức định tuyến, rằng “hãy gửi lưu lượng của tiền tố này đến tôi”. |
| Tổng hợp tuyến | Thông báo một tiền tố ngắn bao trùm nhiều tiền tố dài hơn. Còn gọi là tóm tắt tuyến hay gộp mạng (supernetting). |
| Tuyến cụ thể hơn | Một tiền tố dài hơn nằm bên trong một tiền tố ngắn hơn, chẳng hạn một /23 nằm trong một /20. |
| ISP | Nhà cung cấp dịch vụ Internet (ISP): một mạng bán kết nối Internet cho khách hàng. |
Bảng chuyển tiếp là một danh sách các tiền tố#
Bộ định tuyến phải chọn một liên kết đầu ra cho mỗi datagram, trong vài nano giây. Một dòng bảng cho mỗi địa chỉ đích sẽ có 232, khoảng 4,3 tỷ dòng. Thay vào đó, mỗi dòng bao trùm cả một dải địa chỉ có chung một tiền tố. Đây là bảng chúng ta sẽ dùng, cho một bộ định tuyến có năm liên kết đầu ra:
| Mục | Bao trùm | Các bit tiền tố | Liên kết |
|---|---|---|---|
| 145.64.0.0/16 | 145.64.0.0 đến 145.64.255.255 | 10010001 01000000 | 0 |
| 145.64.96.0/19 | 145.64.96.0 đến 145.64.127.255 | 10010001 01000000 011 | 1 |
| 145.64.100.0/22 | 145.64.100.0 đến 145.64.103.255 | 10010001 01000000 011001 | 2 |
| 145.64.101.128/25 | 145.64.101.128 đến 145.64.101.255 | 10010001 01000000 01100101 1 | 3 |
| 0.0.0.0/0 (mặc định) | tất cả | (không có) | 4 |
Hãy để ý rằng các dải lồng nhau. /25 nằm trong /22, /22 nằm trong /19, và /19 nằm trong /16. Sự lồng nhau đó là lý do một địa chỉ đích có thể khớp nhiều mục cùng lúc.
Các bộ định tuyến thật thực hiện phép tra cứu này bằng phần cứng đặc biệt. Một lựa chọn phổ biến là TCAM, bộ nhớ có thể truy cập theo nội dung ba trạng thái (ternary content-addressable memory), so sánh địa chỉ đích với mọi mục cùng một lúc và trả về đáp án trong thời gian gần như không đổi, bất kể bảng lớn đến đâu.
Khớp từng bước bằng nhị phân#
Phương pháp luôn giống nhau:
- Viết địa chỉ đích ra nhị phân.
- Với mỗi mục, so sánh x bit tiền tố của nó với x bit đầu của địa chỉ đích. Bằng nhau nghĩa là khớp.
- Trong các mục khớp, chọn mục có x lớn nhất.
Địa chỉ đích 145.64.101.200 = 10010001 01000000 01100101 11001000.
/16: 16 bit đầu 10010001 01000000: bằng nhau. Khớp.
/19: 3 bit tiếp theo là 011, và mục đó cần 011. Khớp.
/22: 6 bit đầu của byte thứ ba là 011001, và mục đó cần 011001. Khớp.
/25: toàn bộ byte thứ ba, 01100101, cộng với bit đầu của byte thứ tư, 1. Mục đó cần 01100101 1. Khớp.
Mục mặc định cũng khớp, như lúc nào cũng vậy. Khớp dài nhất: /25, nên datagram đi ra trên liên kết 3.
Địa chỉ đích 145.64.101.20 = 10010001 01000000 01100101 00010100.
/16, /19 và /22 khớp đúng như trước. Nhưng byte thứ tư bắt đầu bằng 0, còn /25 cần 1. Không khớp. Khớp dài nhất: /22, nên là liên kết 2.
Hai địa chỉ này chỉ khác nhau ở byte cuối, vậy mà chúng đi ra trên các liên kết khác nhau. Đó là lý do bạn phải làm việc bằng nhị phân.
| Đích | Các mục khớp | Dài nhất | Liên kết |
|---|---|---|---|
| 145.64.120.5 | /0, /16, /19 | /19 | 1 |
| 145.64.200.1 | /0, /16 | /16 | 0 |
| 145.65.0.1 | chỉ /0 | /0 | 4 |
Địa chỉ thứ ba là một trường hợp suýt khớp: 145.65 khác 145.64 ở bit cuối của byte thứ hai (01000001 so với 01000000), nên ngay cả /16 cũng không khớp.
Vì sao khớp dài nhất thắng#
Một tiền tố dài hơn bao trùm ít địa chỉ hơn, nên nó mang thông tin chính xác hơn. Thường nó được đặt ở đó có chủ đích, như một ngoại lệ được tách ra từ một dải lớn hơn. Trong bảng của chúng ta, có người đã thêm 145.64.101.128/25 chính vì 128 địa chỉ đó không nên theo /22 đến liên kết 2.
Kết quả là mỗi liên kết thực sự nhận dải của chính nó trừ đi mọi dải dài hơn nằm bên trong. Đếm vét cạn trên cả 65.536 địa chỉ trong 145.64.0.0/16 cho ra:
| Liên kết | Mục | Số địa chỉ trong mục | Số địa chỉ thực sự đi đến đó |
|---|---|---|---|
| 3 | /25 | 128 | 128 |
| 2 | /22 | 1,024 | 1,024 − 128 = 896 |
| 1 | /19 | 8,192 | 8,192 − 1,024 = 7,168 |
| 0 | /16 | 65,536 | 65,536 − 8,192 = 57,344 |
Tổng hợp tuyến: một thông báo cho nhiều mạng#
Khớp tiền tố dài nhất bên trong một bộ định tuyến mang lại lợi ích lớn trên khắp Internet. Vì địa chỉ được cấp theo phân cấp (tổ chức đăng ký đến ISP đến khách hàng), mọi khách hàng của một ISP đều nằm trong khối địa chỉ của chính ISP đó. Nên ISP có thể báo cho cả thế giới một tiền tố ngắn thay vì từng khách hàng.
ISP Alpha giữ 84.112.32.0/20 (84.112.32.0 đến 84.112.47.255, 4.096 địa chỉ). Nó đã cấp cho tám khách hàng mỗi người một /23: 84.112.32.0/23, 84.112.34.0/23, 84.112.36.0/23, và cứ thế đến 84.112.46.0/23.
Ở dạng nhị phân, các byte thứ ba là 00100000, 00100010, ... , 00101110. Cả tám đều chung bốn bit đầu 0010 của byte thứ ba. Cộng với 16 bit của hai byte đầu, đó là 20 bit chung: /20.
Vậy Alpha thông báo một tuyến, 84.112.32.0/20, thay vì tám. Bảng của mọi mạng khác chỉ cần một dòng cho Alpha, không phải tám.
Các khối chỉ có thể được gộp thành một thông báo khi ba điều sau đều đúng:
- Các khối phải liền nhau: không có khoảng trống giữa chúng.
- Gộp lại, chúng phải tạo thành một khối thẳng hàng: kích thước là lũy thừa của hai, bắt đầu tại một bội số của kích thước đó.
- Các khối đều phải đi qua cùng chặng kế tiếp.
Vậy 84.112.32.0/23 và 84.112.34.0/23 gộp thành 84.112.32.0/22. Nhưng 84.112.34.0/23 và 84.112.36.0/23 không gộp được, dù chúng sát nhau. Một /22 phải bắt đầu tại bội số của 4 ở byte thứ ba (32, 36, 40, ...), và 34 không phải. Cặp này nằm vắt ngang hai khối /22.
Khi một khách hàng chuyển sang ISP khác#
Giả sử khách hàng có 84.112.40.0/23 rời Alpha để sang ISP thứ hai, Beta, và giữ nguyên địa chỉ. Đánh số lại mọi máy sẽ rất vất vả, nên họ không làm vậy.
Alpha tiếp tục thông báo 84.112.32.0/20, vì nó vẫn phục vụ bảy khách hàng còn lại. Beta bây giờ thông báo 84.112.40.0/23. Các bộ định tuyến khác cuối cùng có cả hai mục: /20 chỉ về phía Alpha và /23 chỉ về phía Beta.
| Đích | Khớp | Dài nhất | Đi đến |
|---|---|---|---|
| 84.112.41.77 | /20 (Alpha) và /23 (Beta) | /23 | Beta |
| 84.112.39.5 | chỉ /20 (Alpha) | /20 | Alpha |
| 84.112.47.200 | chỉ /20 (Alpha) | /20 | Alpha |
Không ai phải thay đổi thông báo của Alpha. /23 cụ thể hơn lặng lẽ thắng cho khách hàng đã chuyển đi, và mọi thứ còn lại vẫn theo /20. Đây là cùng quy tắc với lá thư đi Toronto, ở quy mô Internet.
Bộ định tuyến chuyển tiếp mỗi datagram theo mục trong bảng có tiền tố khớp nhiều bit đầu nhất của địa chỉ đích, và vì tuyến cụ thể nhất luôn thắng, các mạng có thể thông báo một tiền tố tổng hợp cho mọi khách hàng của mình, trong khi khách hàng chuyển đi vẫn được tìm thấy qua tiền tố dài hơn của chính nó.
Luyện tập#
Hãy đổi mỗi địa chỉ đích sang nhị phân trước khi nhìn bảng. Viết đầy đủ byte nơi tiền tố kết thúc.
- Dùng bảng năm liên kết trong bài hướng dẫn này, mỗi địa chỉ đích đi ra trên liên kết nào? (a) 145.64.103.7 (b) 145.64.99.255 (c) 145.64.128.0
- Một bộ định tuyến có các mục sau: 192.0.2.0/24 → A, 192.0.2.64/26 → B, 192.0.2.96/27 → C, 0.0.0.0/0 → D. Mỗi địa chỉ đích đi đâu? (a) 192.0.2.100 (b) 192.0.2.70 (c) 192.0.2.200 (d) 192.0.3.1
- Trong bảng của câu hỏi 2, có bao nhiêu trong 256 địa chỉ của 192.0.2.0/24 thực sự đi đến B?
- Trong bảng năm liên kết, mục 145.64.100.0/22 bị xóa. Bây giờ 145.64.101.20 dùng liên kết nào?
- 57.20.8.0/24, 57.20.9.0/24, 57.20.10.0/24 và 57.20.11.0/24 có thể được thông báo thành một tiền tố không? Nếu được, là tiền tố nào?
- 57.20.9.0/24, 57.20.10.0/24, 57.20.11.0/24 và 57.20.12.0/24 có thể được thông báo thành một tiền tố mà không đồng thời nhận cả những địa chỉ nằm ngoài chúng không?
- Khách hàng có 84.112.44.0/23 chuyển từ ISP Alpha sang ISP Beta. Mỗi ISP thông báo gì cho nó, và các datagram gửi đến 84.112.45.9 và 84.112.47.200 đi đâu?
Lời giải#
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.
- (a) Liên kết 2. (b) Liên kết 1. (c) Liên kết 0. (a) Byte thứ ba 103 =
01100111: bắt đầu bằng011001, nên /22 khớp, và 103 không phải 101, nên /25 không khớp. (b) 99 =01100011: bắt đầu bằng011(/19) nhưng không phải011001. (c) 128 =10000000: không bắt đầu bằng011, nên chỉ /16 khớp. - (a) C. (b) B. (c) A. (d) D. (a) 100 =
01100100khớp /24, /26 (01) và /27 (011); dài nhất là C. (b) 70 =01000110bắt đầu bằng01nhưng không phải011: B. (c) 200 =11001000chỉ khớp /24: A. (d) 192.0.3.1 khác ở byte thứ ba, nên chỉ mục mặc định khớp: D. - 32. /26 của B bao trùm 64 địa chỉ (.64 đến .127), nhưng /27 của C lấy .96 đến .127, tức 32 địa chỉ trong số đó. 64 − 32 = 32 địa chỉ, từ .64 đến .95, đi đến B.
- Liên kết 1. Khi /22 không còn, các mục khớp là /0, /16 và /19. /25 vẫn không khớp, vì byte thứ tư, 20 =
00010100, bắt đầu bằng 0. - Được: 57.20.8.0/22. Các byte thứ ba từ 8 đến 11 là
000010|00đến000010|11: chúng chung 6 bit đầu, và bốn khối lấp đầy đúng một khối thẳng hàng gồm 4, bắt đầu tại 8, một bội số của 4. - Không. 9 đến 12 không thẳng hàng. Tiền tố đơn nhỏ nhất bao trùm cả bốn là 57.20.8.0/21, gồm 2.048 địa chỉ so với 1.024 địa chỉ đang sở hữu. Nếu không muốn nhận quá phần mình có, cách tốt nhất là ba mục: 57.20.9.0/24, 57.20.10.0/23 và 57.20.12.0/24.
- Alpha tiếp tục thông báo 84.112.32.0/20; Beta thông báo 84.112.44.0/23. 84.112.45.9 đi đến Beta; 84.112.47.200 đi đến Alpha. /23 cần byte thứ ba bắt đầu bằng
0010110. 45 =00101101thỏa, và /23 dài hơn /20: Beta. 47 =00101111bắt đầu bằng0010111, nên chỉ /20 khớp: Alpha.
Danh sách kiểm tra trước khi thi#
- ☐ Tôi có thể giải thích vì sao bảng chuyển tiếp chứa các tiền tố chứ không phải từng địa chỉ riêng lẻ.
- ☐ Tôi có thể kiểm tra một mục có khớp một địa chỉ đích hay không bằng cách so sánh bit ở dạng nhị phân.
- ☐ Tôi có thể chọn tiền tố khớp dài nhất từ một bảng, kể cả tuyến mặc định.
- ☐ Tôi có thể tính mỗi liên kết thực sự nhận bao nhiêu địa chỉ khi các mục lồng nhau.
- ☐ Tôi có thể quyết định một tập các khối có thể được tổng hợp hay không, và gọi tên tuyến tổng hợp.
- ☐ Tôi có thể giải thích chuyện gì xảy ra khi một khách hàng giữ nguyên địa chỉ và chuyển sang ISP khác.
Luôn tìm byte nơi tiền tố kết thúc và viết đầy đủ nhị phân của đúng byte đó. Mọi byte khác hoặc hoàn toàn là mạng hoặc hoàn toàn là máy, nên cả câu hỏi được quyết định trong đúng một byte ấy.
Câu hỏi thường gặp#
Khớp tiền tố dài nhất là gì?
Đó là quy tắc bộ định tuyến dùng khi nhiều mục trong bảng chuyển tiếp cùng khớp một địa chỉ đích. Nó dùng mục có tiền tố dài nhất, tức mục khớp nhiều bit đầu nhất, vì mục đó cụ thể nhất.
Thứ tự các mục trong bảng chuyển tiếp có quan trọng không?
Không. Khớp tiền tố dài nhất xét mọi mục khớp và chọn mục dài nhất, dù nó nằm ở đâu. Điều này khác với các danh sách quy tắc dừng ở lần khớp đầu tiên.
Tuyến mặc định là gì?
Là mục 0.0.0.0/0. Độ dài tiền tố của nó bằng không, nên nó khớp mọi địa chỉ, nhưng đó là lần khớp ngắn nhất có thể, nên nó chỉ được dùng khi không mục nào khác phù hợp.
Tổng hợp tuyến là gì?
Tổng hợp tuyến (route aggregation), còn gọi là tóm tắt tuyến (route summarization) hay gộp mạng (supernetting), là thông báo một tiền tố ngắn hơn bao trùm nhiều tiền tố dài hơn. Một ISP có mọi khách hàng nằm trong khối địa chỉ của mình có thể thông báo khối đó một lần thay vì thông báo từng khách hàng riêng.
Chuyện gì xảy ra nếu một khách hàng chuyển sang ISP khác nhưng giữ nguyên địa chỉ?
ISP mới thông báo tiền tố dài hơn của chính khách hàng đó, còn ISP cũ vẫn tiếp tục thông báo tuyến tổng hợp của mình. Các bộ định tuyến thấy cả hai, và khớp tiền tố dài nhất gửi lưu lượng của khách hàng đó đến ISP mới, trong khi mọi thứ còn lại trong tuyến tổng hợp vẫn đến ISP cũ.
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 →