Định tuyến

Trong lĩnh vực mạng máy tính, định tuyến (tiếng Anh: routing hoặc routeing) là quá trình lựa chọn các đường đi trên mạng máy tính để chuyển gửi dữ liệu. Việc định tuyến được áp dụng trong nhiều loại mạng, bao gồm cả mạng điện thoại, mạng liên mạng, Internet, và mạng giao thông.

Định tuyến chỉ ra hướng đi, cách thức di chuyển của các gói tin (dữ liệu) được gắn địa chỉ từ mạng nguồn đến đích thông qua các nút mạng trung gian; các thiết bị phần cứng chuyên dụng được gọi là router (bộ định tuyến). Quá trình định tuyến thường dựa trên bảng định tuyến, một bảng chứa các lộ trình tối ưu đến các điểm đích khác nhau trên mạng. Vì thế, việc xây dựng và duy trì bảng định tuyến trong bộ nhớ của router rất quan trọng để đảm bảo hiệu quả của hệ thống định tuyến.

Định tuyến khác với cầu nối (bridging) ở điểm là nó tập trung vào việc lựa chọn địa chỉ gần nhất và tối ưu nhất trên mạng, từ đó giúp tối ưu hóa quá trình chuyển giao dữ liệu. Do đó, định tuyến thường hoạt động hiệu quả hơn trong các mạng lớn và đã trở thành phương pháp chính trong việc điều phối các đường mạng trên Internet.

Các mạng nhỏ có thể sử dụng bảng định tuyến được cấu hình thủ công, trong khi các mạng lớn với cấu trúc mạng phức tạp và thay đổi liên tục thường sử dụng các phương pháp tự động để xây dựng và duy trì bảng định tuyến. Mạng điện thoại công cộng chuyển mạch (PSTN) thường sử dụng bảng định tuyến được tính toán trước, với các tuyến dự phòng để đảm bảo rằng các lộ trình trực tiếp không bị nghẽn. Định tuyến động cố gắng giải quyết vấn đề này bằng cách tự động xây dựng và duy trì bảng định tuyến dựa trên các thông tin được giao thức định tuyến cung cấp, giúp hệ thống mạng hoạt động gần như tự động trong việc phòng ngừa các sự cố và tắc nghẽn mạng.

Định tuyến động đang chiếm ưu thế trên Internet. Tuy nhiên, cấu hình các giao thức định tuyến thường đòi hỏi nhiều kinh nghiệm; không nên nghĩ rằng kỹ thuật kết nối mạng đã phát triển đến mức hoàn thành tự động việc định tuyến. Kết hợp giữa định tuyến thủ công và tự động là phương pháp hiệu quả nhất.

Các mạng như Internet chia dữ liệu thành các gói tin, mỗi gói tin được đánh nhãn với địa chỉ đích cụ thể và được điều hướng theo lộ trình riêng. Các mạng xoay vòng như mạng điện thoại cũng sử dụng định tuyến để tìm đường cho các cuộc gọi điện thoại, cho phép truyền gửi dữ liệu lớn mà không cần phải lặp lại địa chỉ đích.

Định tuyến IP truyền thống vẫn đơn giản bởi nó sử dụng phương pháp định tuyến bước kế tiếp (next-hop routing); router chỉ xem xét việc gửi gói tin đến đâu mà không quan tâm đến các bước đi tiếp theo của gói tin trên các mạng con. Tuy nhiên, những chiến lược định tuyến phức tạp hơn được áp dụng trong các hệ thống như MPLS, ATM hay Frame Relay, thường được sử dụng như công nghệ hỗ trợ cho mạng IP.

Các loại định tuyến

Thuật toán vector

(giao thức định tuyến vector-khoảng cách)

Thuật toán này sử dụng thuật toán Bellman-Ford. Phương pháp chỉ định một con số, được gọi là chi phí (hoặc trọng số), cho mỗi kết nối giữa các nút trong mạng. Các nút gửi thông tin từ điểm A đến điểm B qua đường đi có tổng chi phí thấp nhất (là tổng của các chi phí của các kết nối được sử dụng giữa các nút).

Thuật toán hoạt động đơn giản. Khi một nút khởi động lần đầu tiên, nó chỉ biết các nút lân cận và chi phí trực tiếp để đến từng nút đó. Thông tin này, bao gồm danh sách các điểm đích, tổng chi phí của từng nút, và bước tiếp theo để gửi dữ liệu đến đó, hình thành bảng định tuyến hoặc bảng khoảng cách. Mỗi nút gửi tổng chi phí của nó đến từng 'hàng xóm' để đến các điểm đích mà nó biết. Các 'hàng xóm' phân tích thông tin này và so sánh với thông tin hiện có của họ; mọi cải tiến sẽ được áp dụng vào bảng định tuyến của họ. Khi hoàn thành, tất cả các nút trên mạng tìm ra bước tiếp theo tối ưu đến mọi điểm đích, với tổng chi phí tốt nhất.

Khi một nút gặp vấn đề, các nút khác sử dụng nút hỏng này trong lộ trình của họ sẽ loại bỏ các lộ trình đó và cập nhật thông tin mới cho bảng định tuyến. Sau đó chúng gửi thông tin này đến tất cả các nút lân cận và lặp lại quá trình. Cuối cùng, tất cả các nút trên mạng nhận được thông tin cập nhật và tìm đường đi mới đến mọi điểm đích còn lại.

Thuật toán trạng thái kết nối

(Các giao thức định tuyến dựa trên trạng thái liên kết)

Khi sử dụng các thuật toán định tuyến trạng thái liên kết, mỗi nút sử dụng dữ liệu cơ bản của nó như một bản đồ của mạng dưới dạng đồ thị. Để làm điều này, mỗi nút gửi thông tin về các nút khác mà nó có thể kết nối đến tổng thể mạng và từng nút đóng góp thông tin một cách độc lập vào bản đồ. Dựa trên bản đồ này, mỗi router sau đó sẽ quyết định về tuyến đường tốt nhất từ nó đến tất cả các nút khác.

Thuật toán thực hiện điều này là Dijkstra, bằng cách xây dựng một cấu trúc dữ liệu khác, dưới dạng cây, trong đó nút hiện tại là gốc và chứa tất cả các nút khác trong mạng. Bắt đầu với một cây ban đầu chỉ chứa chính nó. Sau đó, từ tập hợp các nút chưa được thêm vào cây, nó sẽ thêm nút có chi phí thấp nhất để đến một nút đã có trên cây. Quá trình tiếp tục cho đến khi tất cả các nút đều được thêm vào.

Cây này sau đó được sử dụng để xây dựng bảng định tuyến, cung cấp các bước truyền tiếp tối ưu, ... để từ một nút đến bất kỳ nút nào khác trên mạng.

So sánh các thuật toán định tuyến

Các giao thức định tuyến sử dụng thuật toán vector thường đơn giản và hiệu quả trong các mạng nhỏ và yêu cầu ít (nếu có) giám sát. Tuy nhiên, chúng không hoạt động tốt và có sự lãng phí tài nguyên nhỏ, dẫn đến sự phát triển của các thuật toán trạng thái kết nối phức tạp hơn nhưng hiệu quả hơn để sử dụng trong các mạng lớn. Giao thức vector có vấn đề về đếm đến vô hạn.

Ưu điểm chính của định tuyến bằng trạng thái kết nối là có phản ứng nhanh hơn đối với sự thay đổi kết nối trong một khoảng thời gian cụ thể. Ngoài ra, các gói tin gửi qua mạng trong định tuyến bằng trạng thái kết nối nhỏ hơn so với định tuyến bằng vector. Định tuyến bằng vector yêu cầu truyền thông tin bảng định tuyến đầy đủ, trong khi định tuyến bằng trạng thái kết nối chỉ cần thông tin về 'hàng xóm' của các nút được truyền đi. Do đó, các gói tin này sử dụng tài nguyên mạng ít đáng kể. Nhược điểm chính của định tuyến bằng trạng thái kết nối là yêu cầu lưu trữ và tính toán nhiều hơn so với định tuyến bằng vector.

Giao thức được định tuyến và giao thức định tuyến

Thường xảy ra sự nhầm lẫn giữa 'giao thức được định tuyến' và 'giao thức định tuyến' ('routed protocols' và 'routing protocols').

Giao thức được định tuyến (routed protocols hay routable protocols)

Một giao thức đã được định tuyến là bất kỳ giao thức mạng nào cung cấp đầy đủ thông tin địa chỉ tầng mạng để cho phép gói tin được truyền từ một máy chủ đến máy chủ khác dựa trên sắp xếp địa chỉ, mà không cần biết đường đi toàn bộ từ nguồn đến đích. Giao thức đã được định tuyến xác định cấu trúc và mục đích của các trường trong gói tin. Gói tin thường được chuyển từ hệ thống này sang hệ thống khác. Gần như tất cả các giao thức ở tầng 3 và một số giao thức ở các tầng khác có thể được định tuyến, ví dụ như IP. Điều này có nghĩa là gói tin đã được hướng (có địa chỉ rõ ràng) như một lá thư đã ghi địa chỉ và chỉ cần điều hướng (tìm đường đi đến địa chỉ đó)

Các giao thức ở tầng 2 như Ethernet không thể được định tuyến, vì chúng chỉ chứa địa chỉ tầng liên kết, không đủ để định tuyến: một số giao thức ở tầng cao hơn phụ thuộc vào đây mà không có địa chỉ tầng mạng, chẳng hạn như NetBIOS, cũng không định tuyến được.

Giao thức định tuyến (routing protocols)

Giao thức định tuyến được sử dụng khi triển khai thuật toán định tuyến để trao đổi thông tin giữa các mạng, cho phép các router xây dựng bảng định tuyến một cách linh hoạt. Trong một số trường hợp, giao thức định tuyến có thể chạy đồng thời với giao thức đã được định tuyến: ví dụ, BGP chạy trên TCP. Cần chú ý rằng trong quá trình triển khai, hệ thống không tạo ra sự phụ thuộc giữa giao thức định tuyến và giao thức đã được định tuyến.

Danh sách các giao thức định tuyến

• Giao thức định tuyến trong
  • Router Information Protocol (RIP)
  • Open Shortest Path First (OSPF)
  • Intermediate System to Intermediate System (IS-IS)
  • Hai giao thức sau đây thuộc sở hữu của Cisco, và được hỗ trợ bởi các router Cisco hay những router của những nhà cung cấp mà Cisco đã đăng ký công nghệ:
    • Interior Gateway Routing Protocol (IGRP)
    • Enhanced IGRP (EIGRP)
• Giao thức định tuyến ngoài
  • Exterior Gateway Protocol (EGP)
  • Border Gateway Protocol (BGP)
  • Constrained Shortest Path First (CSPF)

Thông số định tuyến (Routing metrics)

Một thông số định tuyến bao gồm bất kỳ giá trị nào được sử dụng bởi thuật toán định tuyến để xác định liệu một tuyến đường có tốt hơn tuyến đường khác không. Các thông số có thể là những thông tin như băng thông, độ trễ, đếm bước truyền, chi phí đường đi, trọng số, kích thước tối đa gói tin (MTU), độ tin cậy, và chi phí truyền thông. Bảng định tuyến chỉ lưu trữ những tuyến đường tốt nhất có thể, trong khi cơ sở dữ liệu trạng thái kết nối hay topo có thể lưu trữ tất cả các thông tin khác.

Router sử dụng tính năng phân loại mức tin cậy (administrative distance - AD) để chọn đường đi tốt nhất khi có nhiều đường đến cùng một đích theo các giao thức khác nhau. AD xác định độ tin cậy của một giao thức định tuyến. Mỗi giao thức định tuyến được ưu tiên theo thứ tự độ tin cậy từ cao đến thấp, mà mỗi giao thức có giá trị AD thấp hơn sẽ được tin cậy hơn. Ví dụ, OSPF có AD là 110 sẽ được chọn hơn RIP với AD là 120.

Bảng sau đây cho biết sắp xếp mức tin cậy được sử dụng trong các router Cisco

Các lớp giao thức định tuyến

Dựa vào quan hệ của các dòng router với các hệ thống tự trị, có nhiều lớp giao thức định tuyến như sau:

• Giao thức định tuyến trong mạng Ad-hoc xuất hiện trong các mạng không có hoặc ít phương tiện truyền dẫn.
• Interior Gateway Protocols (IGPs) trao đổi thông tin định tuyến trong một AS. Các ví dụ thường thấy là:
  • IGRP (Interior Gateway Routing Protocol)
  • EIGRP (Enhanced Interior Gateway Routing Protocol)
  • OSPF (Open Shortest Path First)
  • RIP (Routing Information Protocol)
  • RSMLT
  • IS-IS (Intermediate System to Intermediate System)

Chú ý: theo nhiều tài liệu của Cisco, EIGRP không phân lớp như giao thức trạng thái kết nối.

• Exterior Gateway Protocols (EGPs) định tuyến giữa các AS. EGPs gồm:
  • EGP (giao thức cũ để nối mạng Internet trước đây, bây giờ đã lỗi thời)
  • BGP (Border Gateway Protocol: phiên bản hiện tại, BGPv4, có từ khoảng năm 1995)