Thuật toán định tuyến (routing algorithm) là tập hợp các quy tắc và phép tính logic được bộ định tuyến thực thi nhằm xác định đường đi tối ưu cho các gói dữ liệu từ nút nguồn đến nút đích qua mạng máy tính. Dựa trên mô hình biểu diễn mạng dưới dạng đồ thị có trọng số, thuật toán định tuyến đóng vai trò trung tâm trong việc đảm bảo lưu lượng thông tin được chuyển tiếp liên tục, hiệu quả, tránh tắc nghẽn và tự động thích ứng với các thay đổi về cấu trúc mạng hoặc sự cố phần cứng. Bài viết này trình bày toàn diện về cơ sở lý thuyết đồ thị, hai trường phái định tuyến kinh điển, bước chuyển biến lịch sử trên mạng ARPANET, các thách thức về độ trễ hội tụ liên miền cùng triển vọng phát triển kiến trúc mạng hiện đại.
Bản chất lý thuyết đồ thị và bài toán tìm đường đi ngắn nhất
Trong khoa học máy tính và kỹ thuật mạng viễn thông, cấu trúc liên kết của một mạng chuyển mạch gói được mô hình hoá trừu tượng dưới dạng một đồ thị gồm tập hợp các đỉnh đại diện cho các nút mạng (như bộ định tuyến, máy chủ, thiết bị chuyển mạch) và tập hợp các cạnh đại diện cho các liên kết truyền thông vật lý hoặc logic kết nối giữa các nút. Mỗi cạnh trong đồ thị được gán một giá trị trọng số dương thể hiện chi phí truyền thông, giá trị này có thể tương ứng với độ trễ truyền dẫn, nghịch đảo của băng thông, chi phí tài chính hoặc số chặng truyền tải.
Bài toán định tuyến căn bản được quy về bài toán tìm đường đi có tổng chi phí nhỏ nhất giữa hai nút bất kỳ trong đồ thị. Để giải quyết bài toán này, các nhà toán học và khoa học máy tính đã phát triển các phương pháp tính toán tối ưu hoá rời rạc, đặt nền móng cho toàn bộ hạ tầng giao tiếp Internet toàn cầu. Tuỳ thuộc vào phạm vi thông tin mà mỗi nút sở hữu và phương thức phối hợp trao đổi dữ liệu, các thuật toán định tuyến được phân chia thành những trường phái kiến trúc khác biệt.
Hai trường phái thuật toán định tuyến kinh điển
Trong phạm vi một hệ thống tự trị nội miền, hai trường phái thuật toán định tuyến cơ bản và phổ biến nhất là thuật toán vectơ khoảng cách (distance-vector routing) và thuật toán trạng thái liên kết (link-state routing).
Thuật toán vectơ khoảng cách dựa trên nguyên lý tối ưu hoá đệ trình bởi Richard Bellman công bố năm 1958 trên tạp chí Quarterly of Applied Mathematics, được phát triển thành thuật toán Bellman-Ford hoàn chỉnh. Theo cơ chế này, mỗi bộ định tuyến chỉ lưu trữ và duy trì một vectơ khoảng cách thể hiện chi phí ước tính từ chính nó đến tất cả các nút đích có thể tiếp cận trong mạng, cùng với nút chặng kế tiếp để chuyển tiếp gói tin. Định kỳ hoặc khi có biến động liên kết, mỗi nút gửi toàn bộ vectơ khoảng cách của mình cho các nút láng giềng trực tiếp. Nút nhận thông tin sẽ áp dụng phương trình Bellman để cập nhật bảng khoảng cách nếu tìm thấy đường đi mới có chi phí thấp hơn qua người láng giềng đó. Ưu điểm nổi bật của thuật toán vectơ khoảng cách là tính đơn giản, không đòi hỏi bộ định tuyến phải có năng lực xử lý mạnh hay bộ nhớ lớn. Tuy nhiên, nhược điểm lớn nhất là tốc độ hội tụ chậm và dễ rơi vào hiện tượng đếm đến vô cùng khi xảy ra sự cố đứt gãy liên kết, đòi hỏi phải áp dụng các kỹ thuật bổ trợ như phân tách chân trời và nhiễm độc ngược.
Ngược lại hoàn toàn với vectơ khoảng cách, thuật toán trạng thái liên kết dựa trên giải thuật tìm đường đi ngắn nhất do Edsger W. Dijkstra công bố năm 1959 trên tạp chí Numerische Mathematik. Trong mô hình này, mỗi bộ định tuyến chỉ gửi thông tin trạng thái của các liên kết trực tiếp kết nối với chính nó (gồm danh tính láng giềng và chi phí liên kết tương ứng). Gói tin trạng thái liên kết được phát tán rộng khắp tới toàn bộ các nút trong mạng thông qua kỹ thuật làm tràn có kiểm soát. Kết quả là mỗi bộ định tuyến đều xây dựng được một cơ sở dữ liệu trạng thái liên kết hoàn toàn giống nhau, phản ánh sơ đồ cấu trúc hoàn chỉnh của toàn mạng. Từ cơ sở dữ liệu này, mỗi nút độc lập thực thi thuật toán Dijkstra với nút gốc là chính nó để xây dựng cây đường đi ngắn nhất tới tất cả các nút khác và nạp kết quả vào bảng chuyển tiếp gói tin.
| Tiêu chí so sánh | Thuật toán vectơ khoảng cách | Thuật toán trạng thái liên kết |
|---|---|---|
| Tri thức về mạng tại mỗi nút | Chỉ biết thông tin về nút láng giềng trực tiếp và vectơ chi phí | Nắm giữ sơ đồ cấu trúc topo hoàn chỉnh của toàn bộ mạng |
| Giải thuật toán học cốt lõi | Thuật toán Bellman-Ford (Richard Bellman, 1958) | Thuật toán đường đi ngắn nhất (Edsger W. Dijkstra, 1959) |
| Tốc độ hội tụ khi mạng thay đổi | Chậm, có nguy cơ vòng lặp định tuyến cục bộ tạm thời | Nhanh, tính toán độc lập tại từng nút sau khi lan truyền xong |
| Tài nguyên tính toán và bộ nhớ | Thấp, phù hợp với thiết bị định tuyến cấu hình đơn giản | Đòi hỏi bộ nhớ lớn hơn và năng lực CPU tính toán cây đồ thị |
| Hiện tượng bệnh lý điển hình | Vấn đề đếm đến vô cùng khi liên kết ngừng hoạt động | Lao dao định tuyến nếu chỉ số đo lường liên kết biến thiên liên tục |
Bước ngoặt chuyển đổi trên mạng ARPANET và bài học thực tiễn
Sự vượt trội của thuật toán trạng thái liên kết đã được minh chứng rõ nét qua lịch sử phát triển mạng tiền thân của Internet. Ban đầu, mạng ARPANET sử dụng thuật toán vectơ khoảng cách dựa trên nguyên mẫu Bellman-Ford phân tán. Khi quy mô mạng mở rộng và lưu lượng truyền tải tăng mạnh, thuật toán cũ bộc lộ những khiếm khuyết trầm trọng: độ trễ hàng đợi dao động khiến thông tin khoảng cách mất tính ổn định, các vòng lặp định tuyến xuất hiện thường xuyên và thời gian hội tụ kéo dài khiến nhiều gói tin bị huỷ bỏ vô cớ.
Để giải quyết triệt để cuộc khủng hoảng định tuyến này, McQuillan và cộng sự (1980) đã công bố trên tạp chí IEEE Transactions on Communications thiết kế của thuật toán định tuyến trạng thái liên kết mới cho mạng ARPANET. Trong kiến trúc mới, mỗi nút mạng đo lường độ trễ thực tế trung bình của các gói tin trên từng liên kết kết nối trực tiếp, sau đó đóng gói dữ liệu này vào các gói tin trạng thái liên kết và làm tràn khắp toàn mạng. Mỗi nút áp dụng thuật toán Dijkstra để tính toán lại bảng định tuyến độc lập. Thiết kế thuật toán của McQuillan và cộng sự (1980) đã loại bỏ hoàn toàn hiện tượng vòng lặp định tuyến mạn tính, giảm thiểu dao động lưu lượng và tạo nên bước chuyển mình nền tảng cho sự ra đời của các giao thức định tuyến trạng thái liên kết chuẩn mực sau này như OSPF (Open Shortest Path First) và IS-IS (Intermediate System to Intermediate System).
Định tuyến liên miền và thách thức độ trễ hội tụ trên Internet
Khi mạng Internet mở rộng thành cấu trúc phân cấp gồm hàng chục nghìn hệ thống tự trị độc lập do các nhà cung cấp dịch vụ viễn thông khác nhau quản lý, các thuật toán tìm đường đi ngắn nhất đơn thuần không còn đáp ứng được yêu cầu vì không thể bao hàm các chính sách thương mại, thoả thuận chia sẻ lưu lượng và quy định pháp lý giữa các tổ chức. Để giải quyết bài toán định tuyến liên miền, giao thức cổng biên BGP (Border Gateway Protocol) áp dụng trường phái vectơ đường đi (path-vector routing).
Thay vì chỉ trao đổi chi phí dạng số vô hướng, các bộ định tuyến BGP trao đổi toàn bộ danh sách chuỗi các hệ thống tự trị mà gói tin phải đi qua để đến được dải mạng đích. Việc đính kèm chuỗi đường đi này cho phép bộ định tuyến phát hiện ngay lập tức các vòng lặp nếu số hiệu hệ thống tự trị của chính nó xuất hiện trong danh sách, từ đó loại bỏ tuyến đường lỗi trước khi cập nhật.
Mặc dù vectơ đường đi ngăn chặn được vòng lặp vô hạn, quá trình hội tụ của định tuyến liên miền lại phát sinh những khiếm khuyết phức tạp. Nghiên cứu thực nghiệm quy mô lớn của Labovitz và cộng sự (2001) trên tạp chí IEEE/ACM Transactions on Networking đã chứng minh hiện tượng chậm trễ nghiêm trọng trong quá trình hội tụ của giao thức BGP trên mạng Internet toàn cầu. Labovitz và cộng sự (2001) ghi nhận rằng khi một liên kết bị đứt hoặc một tuyến đường bị rút lại, các bộ định tuyến biên không hội tụ ngay lập tức mà trải qua quá trình thăm dò đường đi bệnh lý, thử nghiệm tuần tự qua hàng loạt đường đi dự phòng kém tối ưu trước khi nhận ra đích đến thực sự không thể tiếp cận. Quá trình thăm dò này khiến thời gian hội tụ định tuyến liên miền kéo dài trung bình khoảng 3 phút sau sự cố rút đường, làm rơi rụng hàng triệu gói tin và làm suy giảm chất lượng dịch vụ truyền thông thời gian thực.
Những thách thức kỹ thuật và vấn đề khoa học còn mở
Sự bùng nổ của các trung tâm dữ liệu siêu quy mô, mạng truyền thông vệ tinh tầm thấp và điện toán đám mây biên đang đặt ra những bài toán hóc búa cho các thuật toán định tuyến truyền thống:
- Khả năng mở rộng bảng định tuyến toàn cầu: Số lượng tiền tố mạng trong bảng định tuyến Internet liên tục gia tăng, đòi hỏi các thuật toán nén bảng chuyển tiếp và phần cứng tra cứu tốc độ cao để không làm quá tải bộ nhớ TCAM (Ternary Content-Addressable Memory) trên các bộ định tuyến lõi.
- Định tuyến đa mục tiêu bảo đảm chất lượng dịch vụ: Việc tìm kiếm đường đi đồng thời thoả mãn nhiều ràng buộc độc lập như độ trễ tối thiểu, băng thông tối đa và tỷ lệ mất gói thấp nhất là bài toán NP-đầy đủ, đòi hỏi việc áp dụng các thuật toán xấp xỉ và heuristic thông minh.
- Định tuyến thích ứng trong mạng điều khiển bằng phần mềm (Software-Defined Networking - SDN): Kiến trúc tách rời mặt phẳng điều khiển và mặt phẳng chuyển tiếp cho phép áp dụng các thuật toán tối ưu hoá tập trung dựa trên lý thuyết đồ thị động và học máy. Tổng quan của Bouchmal và cộng sự (2023) trên tạp chí Frontiers in Communications and Networks chỉ ra rằng mặc dù học máy nâng cao hiệu quả phân phối lưu lượng, tốc độ hội tụ định tuyến và độ phức tạp tính toán thời gian thực khi cấu trúc topo biến động lớn vẫn là rào cản kỹ thuật then chốt.