Kurose và Ross, Computer Networking: A Top-Down Approach, mục 5.3, đối chiếu với RFC 2328 (OSPF Version 2), RFC 1930 (Guidelines for creation, selection, and registration of an Autonomous System) và RFC 6793 (BGP Support for Four-Octet Autonomous System (AS) Number Space). Mọi chi phí và đường đi bên dưới đều được tính bằng mã.
Trước hết hãy học hai lý do cho hệ tự trị: quy mô và tính tự chủ. Sau đó xem OSPF như bài hướng dẫn về Dijkstra cộng thêm vài chi tiết thực tế. Cuối cùng, hãy vẽ lại hình các vùng từ trí nhớ và gắn nhãn cho mọi loại bộ định tuyến.
Nhiều bài giảng gọi là “boundary router” (bộ định tuyến biên) cho bộ định tuyến nối mạng OSPF với các hệ tự trị khác. Tên chuẩn, trong RFC 2328, là AS boundary router (ASBR). Cả hai đều chỉ cùng một bộ định tuyến. Đây là bộ định tuyến cổng (gateway router) của sách giáo khoa, nhìn từ bên trong OSPF.
Hình dung: xe buýt thành phố và chuyến bay#
Hãy hình dung việc đi lại giữa các thành phố. Trong thành phố của bạn, công ty xe buýt biết từng con phố. Họ lập tuyến theo cách họ muốn, và không thành phố nào khác quan tâm đến chuyện đó.
Giữa các thành phố, bạn không cần biết các con phố của thành phố mình bay tới. Bạn chỉ cần biết sân bay nào nối tới đó.
Internet hoạt động giống như vậy. Mạng của mỗi tổ chức là một thành phố với sơ đồ xe buýt riêng: đó là định tuyến intra-AS, và OSPF là một trong những sơ đồ được dùng rộng rãi nhất. Các liên kết giữa các mạng là những chuyến bay: đó là định tuyến inter-AS, do BGP thực hiện, chủ đề của bài hướng dẫn tiếp theo.
Từ vựng, trước khi dùng đến#
| Thuật ngữ | Ý nghĩa |
|---|---|
| Hệ tự trị (AS) | Một nhóm bộ định tuyến do một tổ chức vận hành theo một chính sách định tuyến. “Autonomous” nghĩa là tự quản. |
| ASN | Số hiệu hệ tự trị (autonomous system number): số duy nhất dùng để gọi tên một AS. |
| Bộ định tuyến cổng (gateway router) | Bộ định tuyến ở rìa của một AS, có liên kết tới một bộ định tuyến trong AS khác. |
| Định tuyến intra-AS | Định tuyến giữa các bộ định tuyến bên trong một AS. |
| Định tuyến inter-AS | Định tuyến giữa các AS khác nhau. Trên Internet việc này luôn là BGP. |
| OSPF | Open Shortest Path First: giao thức intra-AS dạng trạng thái liên kết. “Open” nghĩa là đặc tả của nó được công khai. |
| LSA | Thông báo trạng thái liên kết (link-state advertisement): thông điệp trong đó một bộ định tuyến liệt kê các liên kết của chính nó và chi phí của chúng. |
| Flooding | Gửi một thông điệp tới mọi bộ định tuyến trong một khu vực, mỗi bộ định tuyến chuyển tiếp nó cho các láng giềng của mình. |
| Chi phí liên kết (link cost) | Một con số trên mỗi liên kết, còn gọi là trọng số (weight). OSPF tìm đường có tổng chi phí thấp nhất. |
| Vùng (area) | Một phần của mạng OSPF. LSA chỉ được flood bên trong vùng của chúng. |
| Xương sống (backbone) | Vùng đặc biệt, vùng 0, nối tất cả các vùng khác. |
| Bộ định tuyến biên vùng (area border router, ABR) | Bộ định tuyến nằm trong cả vùng của nó lẫn vùng xương sống, chuyển các bản tóm tắt giữa hai bên. |
Vì sao một sơ đồ định tuyến phẳng không thể hoạt động#
Hai bài hướng dẫn trước giả định mọi bộ định tuyến đều ngang nhau và biết về mọi bộ định tuyến khác. Điều đó không đúng trên Internet thật, vì hai lý do.
Quy mô. Có quá nhiều đích đến. Giả sử mỗi bộ định tuyến giữ một mục cho mỗi mạng /24 có thể có trong IPv4 (một /24 là một khối 256 địa chỉ). Đó là 224 = 16.777.216 mục, và mọi thay đổi ở bất kỳ đâu đều phải đến được mọi bộ định tuyến. Việc flood sẽ làm nghẽn các liên kết, và vectơ khoảng cách sẽ không bao giờ hội tụ (converge), tức là không bao giờ đạt được các đáp án ổn định.
Tính tự chủ về quản trị. Internet là mạng của các mạng, mỗi mạng có một chủ sở hữu. Một công ty hoặc một ISP (nhà cung cấp dịch vụ Internet) muốn vận hành mạng của mình theo cách riêng, và có thể muốn giấu cách mạng được xây dựng.
Cách giải quyết là nhóm các bộ định tuyến thành hệ tự trị. Một AS thường là một tổ chức, dù một ISP lớn có thể chia mạng của mình thành nhiều AS. ASN ban đầu là số 16 bit, cho phép 216 = 65.536 số. Giờ đây chúng có thể là 32 bit, cho phép 232 = 4.294.967.296. Bên trong một AS, mọi bộ định tuyến chạy cùng một giao thức intra-AS, do chủ sở hữu chọn. Giữa các AS, mọi người chạy cùng một giao thức inter-AS, để có thể hiểu nhau.
Định tuyến intra-AS so với inter-AS#
| Định tuyến intra-AS | Định tuyến inter-AS | |
|---|---|---|
| Giữa những bộ định tuyến nào | Các bộ định tuyến trong cùng một AS | Các bộ định tuyến cổng trong các AS khác nhau |
| Ai chọn giao thức | Chủ sở hữu AS, hoàn toàn tự do | Không ai tự quyết một mình: toàn bộ Internet dùng BGP |
| Mục tiêu chính | Hiệu năng: đường có chi phí thấp | Chính sách trước hết: ai được chở lưu lượng của ai |
| Ví dụ | OSPF, IS-IS (một giao thức trạng thái liên kết khác), RIP | BGP |
Hai việc của định tuyến inter-AS
Hãy lấy một AS có hai bộ định tuyến cổng, một nối tới AS X và một nối tới AS Y. Với lưu lượng đi ra khỏi AS, nó phải:
- Học những đích đến nào có thể tới được qua AS X và những đích nào qua AS Y.
- Truyền hiểu biết đó tới mọi bộ định tuyến bên trong AS, để mỗi bộ có thể hướng về đúng cổng.
Nếu một AS chỉ có một cổng thì không có gì để chọn. Các bộ định tuyến của nó có thể dùng một tuyến mặc định (default route): “bất cứ thứ gì tôi không nhận ra, gửi về phía cổng”.
Thêm một cái tên nữa: RIP (Routing Information Protocol) là một giao thức intra-AS vectơ khoảng cách cũ hơn. Mỗi liên kết có chi phí 1, và 16 nghĩa là “không tới được”, nên đường đi bị giới hạn ở 15 bước nhảy. Nó chỉ phù hợp với mạng nhỏ.
OSPF: định tuyến trạng thái liên kết, chạy thực tế#
Mỗi bộ định tuyến OSPF làm bốn việc:
- Mô tả các liên kết của mình trong một LSA: từng liên kết và chi phí của nó.
- Flood LSA tới mọi bộ định tuyến trong AS (hoặc vùng). Nó làm việc này mỗi khi một liên kết thay đổi, và dù sao cũng ít nhất mỗi 30 phút một lần.
- Dựng bản đồ. Từ tất cả các LSA, mọi bộ định tuyến dựng cùng một bản đồ đầy đủ, gọi là cơ sở dữ liệu trạng thái liên kết (link-state database).
- Chạy Dijkstra từ chính nó tới mọi mạng con, và điền vào bảng chuyển tiếp của mình từ kết quả.
Các thông điệp OSPF đi trực tiếp bên trong các datagram IP, với số hiệu giao thức tầng trên là 89. Bên dưới không có TCP hay UDP, nên OSPF tự xác nhận các thông điệp của mình.
Ai đặt chi phí liên kết?
Quản trị viên mạng. OSPF tìm các đường có chi phí thấp nhất nhưng không nói cách chọn chi phí. Đặt mọi chi phí bằng 1 cho ra định tuyến ít bước nhảy nhất. Một thói quen phổ biến là làm cho các liên kết nhanh có chi phí thấp:
chi phí = băng thông tham chiếu ÷ băng thông liên kết, không bao giờ nhỏ hơn 1
Lấy một băng thông tham chiếu (tốc độ được tính là chi phí 1) bằng 1.000 Mbps. Một liên kết 10 Mbps có chi phí 1.000 ÷ 10 = 100, một liên kết 100 Mbps có chi phí 10, và một liên kết 1 Gbps có chi phí 1.
Năm bộ định tuyến, R1 đến R5, được nối bằng sáu liên kết. Các liên kết 1 Gbps, mỗi liên kết chi phí 1, là R1–R3, R2–R4 và R3–R5. Các liên kết 100 Mbps, mỗi liên kết chi phí 10, là R1–R2 và R3–R4. Liên kết 10 Mbps duy nhất, chi phí 100, là R4–R5.
Dijkstra tại R1 thêm R3 (chi phí 1), rồi R5 (2, qua R3), rồi R2 (10), rồi R4 (11). R4 có hai đường chi phí 11: R1→R2→R4 (10 + 1) và R1→R3→R4 (1 + 10).
| Đích | Chi phí từ R1 | Đường đi | R1 gửi về phía |
|---|---|---|---|
| R2 | 10 | R1→R2 | R2 |
| R3 | 1 | R1→R3 | R3 |
| R4 | 11 | R1→R2→R4 và R1→R3→R4 | R2 và R3 (OSPF có thể chia lưu lượng) |
| R5 | 2 | R1→R3→R5 | R3 |
Chi phí giống như vô lăng để lái. Nâng cấp R1–R2 lên 1 Gbps thì chi phí của nó giảm xuống 1. Khi đó R4 có chi phí 2 chỉ qua R2, và thế hòa không còn.
Công thức chi phí không thuộc chuẩn OSPF. Một mặc định của nhà cung cấp được dùng rộng rãi lấy băng thông tham chiếu là 100 Mbps. Khi đó một liên kết 100 Mbps và một liên kết 1 Gbps đều có chi phí 1, vì không có gì xuống dưới 1, và OSPF không phân biệt được chúng. Vì vậy quản trị viên nâng băng thông tham chiếu lên trên các mạng hiện đại.
Các tính năng “nâng cao”
- Bảo mật. Các thông điệp có thể được xác thực: bộ định tuyến kiểm tra một mật khẩu chung hoặc một mã băm mật mã trước khi tin chúng. Khi đó người ngoài không thể chèn các LSA giả để kéo lưu lượng đi qua máy của họ.
- Nhiều đường cùng chi phí. Khi các đường hòa nhau, như R1→R4 ở trên, OSPF có thể dùng cả hai cùng lúc.
- Unicast và multicast tích hợp. Một phần mở rộng, MOSPF, dùng lại cùng bản đồ cho multicast (một người gửi tới một nhóm). Ngày nay nó hiếm khi được dùng.
- Phân cấp bên trong một AS, bằng các vùng.
OSPF phân cấp: các vùng và xương sống#
Một AS lớn có vấn đề quy mô ở dạng thu nhỏ: mọi thay đổi đều được flood khắp nơi, và mọi bộ định tuyến chạy Dijkstra trên toàn bộ bản đồ. Vì vậy quản trị viên có thể chia AS thành các vùng. LSA chỉ được flood bên trong vùng của chúng, và mỗi bộ định tuyến chỉ biết bản đồ của vùng mình. Đúng một vùng là xương sống (vùng 0). Mọi vùng khác nối tới nó, và lưu lượng giữa hai vùng luôn đi qua nó.
| Loại bộ định tuyến | Vị trí | Tác dụng |
|---|---|---|
| Bộ định tuyến nội bộ (internal router) | Mọi liên kết của nó nằm trong một vùng (một bộ định tuyến hoàn toàn nằm trong vùng 0 vừa là bộ định tuyến nội bộ vừa là bộ định tuyến xương sống) | Chỉ định tuyến trong vùng của nó. |
| Bộ định tuyến biên vùng (area border router, ABR) | Trong vùng của nó và trong xương sống | Tóm tắt các mạng của vùng mình ở xa bao nhiêu, và quảng bá điều đó tới xương sống, đồng thời chuyển các bản tóm tắt của xương sống vào vùng của mình. |
| Bộ định tuyến xương sống (backbone router) | Bên trong xương sống | Định tuyến lưu lượng giữa các vùng. Mọi ABR cũng là một bộ định tuyến xương sống. |
| Bộ định tuyến biên AS (AS boundary router, ASBR) | Ở rìa của AS | Trao đổi tuyến với các AS khác (trên Internet, dùng BGP), và đưa chúng vào OSPF. |
Một máy trong vùng 1 gửi tới một máy trong vùng 3 của cùng AS. Datagram đi qua các bộ định tuyến nội bộ của vùng 1 tới ABR của vùng 1, băng qua xương sống tới ABR của vùng 3, rồi đi qua các bộ định tuyến nội bộ của vùng 3. Nó không bao giờ vào vùng 2.
Giả sử một AS có 200 bộ định tuyến được chia thành bốn vùng, mỗi vùng 50. Khi một liên kết bên trong vùng 2 hỏng, LSA chi tiết được flood tới khoảng 50 bộ định tuyến, không phải 200. Các vùng khác chỉ thấy một bản tóm tắt mới từ ABR của vùng 2.
Internet được chia thành các hệ tự trị vì quy mô và tính tự chủ về quản trị; bên trong mỗi AS, một giao thức như OSPF flood các thông báo trạng thái liên kết, chạy Dijkstra trong mọi bộ định tuyến dựa trên chi phí do quản trị viên đặt, và có thể chia một AS lớn thành các vùng nối với nhau bằng xương sống, còn BGP định tuyến giữa các AS.
Luyện tập#
Khi một câu hỏi nhắc đến R1 đến R5, hãy dùng mạng năm bộ định tuyến trong phần OSPF. Hãy chạy Dijkstra trên giấy trước.
- Nêu hai lý do Internet không được chạy như một hệ thống định tuyến phẳng duy nhất, mỗi lý do một câu.
- Với băng thông tham chiếu 1.000 Mbps, mỗi liên kết nhận chi phí OSPF bao nhiêu? (a) 10 Mbps, (b) 100 Mbps, (c) 1 Gbps, (d) 10 Gbps.
- Liên kết R3–R4 hỏng. Đường có chi phí thấp nhất mới của R1 tới R4 là gì, và chi phí bao nhiêu?
- Trong mạng ban đầu, quản trị viên nâng chi phí của R3–R5 từ 1 lên 200. Giờ đường (hoặc các đường) có chi phí thấp nhất của R1 tới R5 là gì, và chi phí bao nhiêu?
- Mạng của một công ty nhỏ chỉ có đúng một liên kết tới ISP của mình. Các bộ định tuyến nội bộ của nó có cần các tuyến của thế giới bên ngoài không?
- Một mạng OSPF có bốn vùng cộng với xương sống. Một liên kết bên trong vùng 4 đổi chi phí. Những bộ định tuyến nào nhận LSA chi tiết?
- Một datagram đi từ một máy trong vùng 2 tới một máy trong vùng 1 của cùng AS. Hãy liệt kê, theo thứ tự, các loại bộ định tuyến mà nó đi qua.
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.
- Quy mô và tính tự chủ về quản trị. Quy mô: quá nhiều đích đến để mọi bộ định tuyến lưu trữ và cập nhật, và các thông điệp định tuyến sẽ làm nghẽn các liên kết. Tính tự chủ: mỗi tổ chức muốn tự vận hành, và có thể muốn giấu, mạng của mình.
- (a) 100, (b) 10, (c) 1, (d) 1. 1.000 ÷ 10 = 100 và 1.000 ÷ 100 = 10. 1.000 ÷ 1.000 = 1. Với 10 Gbps, 1.000 ÷ 10.000 = 0,1, nhưng chi phí không thể nhỏ hơn 1, nên nó cũng là 1.
- R1→R2→R4, chi phí 11. Đường chi phí 11 còn lại dùng R3–R4, mà giờ đã mất. Tuyến khác duy nhất, R1→R3→R5→R4, có chi phí 1 + 1 + 100 = 102.
- Hai đường hòa nhau ở chi phí 111: R1→R2→R4→R5 và R1→R3→R4→R5. 10 + 1 + 100 = 111 và 1 + 10 + 100 = 111. Đường cũ R1→R3→R5 giờ có chi phí 1 + 200 = 201. OSPF có thể chia lưu lượng qua hai đường chi phí 111.
- Không. Một tuyến mặc định là đủ. Với một cổng thì không có lựa chọn nào để đưa ra, nên mọi thứ không nhận ra đều đi về phía cổng.
- Chỉ các bộ định tuyến trong vùng 4, kể cả ABR của nó. Việc flood ở lại bên trong vùng của chúng. Các vùng khác chỉ thấy bản tóm tắt cập nhật mà ABR chuyển tới xương sống.
- Các bộ định tuyến nội bộ vùng 2, ABR của vùng 2, các bộ định tuyến xương sống, ABR của vùng 1, các bộ định tuyến nội bộ vùng 1. Lưu lượng giữa hai vùng luôn băng qua xương sống.
Danh sách kiểm tra trước khi thi#
- ☐ Tôi nêu được hai lý do cho hệ tự trị: quy mô và tính tự chủ về quản trị.
- ☐ Tôi định nghĩa được AS, ASN và bộ định tuyến cổng, và nói được khi nào một tuyến mặc định là đủ.
- ☐ Tôi so sánh được định tuyến intra-AS và inter-AS và gọi tên được các giao thức của mỗi loại.
- ☐ Tôi liệt kê được bốn bước của một bộ định tuyến OSPF, và nói được rằng OSPF chạy trên IP với số giao thức 89.
- ☐ Tôi đổi được băng thông thành chi phí OSPF, và nói được vì sao công thức khác nhau giữa các nhà cung cấp.
- ☐ Tôi chạy được Dijkstra trên một mạng OSPF nhỏ và nhận ra các đường cùng chi phí.
- ☐ Tôi vẽ được OSPF phân cấp và gắn nhãn các bộ định tuyến nội bộ, ABR, xương sống và ASBR.
Với bất kỳ câu hỏi định tuyến nào, trước hết hãy hỏi: bên trong một AS, hay giữa các AS? Bên trong nghĩa là OSPF, IS-IS hoặc RIP, nhắm tới chi phí thấp. Giữa các AS nghĩa là BGP, nhắm tới chính sách.
Câu hỏi thường gặp#
Hệ tự trị (autonomous system) là gì?
Hệ tự trị là một nhóm bộ định tuyến thuộc cùng một quyền quản trị với một chính sách định tuyến, thường là một tổ chức như nhà cung cấp dịch vụ Internet (ISP) hoặc một công ty. Mỗi AS có một số hiệu duy nhất, và Internet là mạng lưới của hàng nghìn AS như vậy.
Định tuyến intra-AS và inter-AS khác nhau thế nào?
Định tuyến intra-AS tìm đường bên trong một hệ tự trị, dùng giao thức do chủ sở hữu chọn, chẳng hạn OSPF. Định tuyến inter-AS tìm đường giữa các hệ tự trị, và toàn bộ Internet dùng một giao thức duy nhất cho việc này: BGP.
OSPF hoạt động như thế nào?
Mỗi bộ định tuyến OSPF flood các thông báo trạng thái liên kết (link-state advertisement) liệt kê các liên kết của nó và chi phí của chúng tới mọi bộ định tuyến trong vùng của nó. Mọi bộ định tuyến dựng cùng một bản đồ từ các thông báo đó, chạy thuật toán Dijkstra để tìm đường có chi phí thấp nhất tới mọi mạng con, rồi điền vào bảng chuyển tiếp của mình. Quản trị viên đặt chi phí liên kết.
Vùng OSPF (OSPF area) là gì?
Vùng là một phần của mạng OSPF. Các thông báo trạng thái liên kết chỉ được flood trong vùng của chúng, và các bộ định tuyến biên vùng chuyển bản tóm tắt tới vùng xương sống (backbone), vùng 0, nối tất cả các vùng lại. Điều này giữ cho việc flood và Dijkstra ở quy mô nhỏ trong một mạng lớn.
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 →