Trong ngành mạng máy tính, định tuyến (tiếng Anh: routing hay routeing) là quá trình chọn lựa các đường đi trên một mạng máy tính để gửi dữ liệu qua đó. Việc định tuyến được thực hiện cho nhiều loại mạng, trong đó có mạng điện thoại, liên mạng, Internet, mạng giao thông.
Routing chỉ ra hướng, sự chuyển dời của những gói ( tài liệu ) được đánh địa chỉ từ mạng nguồn của chúng, hướng đến đích cuối trải qua những node trung gian ; thiết bị phần cứng chuyên dùng được gọi là router ( bộ định tuyến ). Tiến trình định tuyến thường chỉ hướng đi dựa vào bảng định tuyến, đó là bảng chứa những lộ trình tốt nhất đến những đích khác nhau trên mạng. Vì vậy việc kiến thiết xây dựng bảng định tuyến, được tổ chức triển khai trong bộ nhớ của router, trở nên vô cùng quan trọng cho việc định tuyến hiệu suất cao .Routing khác với bridging ( bắc cầu ) ở chỗ trong trách nhiệm của nó thì những cấu trúc địa chỉ gợi nên sự thân mật của những địa chỉ tương tự như trong mạng, qua đó cho phép nhập liệu một bảng định tuyến đơn để miêu tả lộ trình đến một nhóm những địa chỉ. Vì thế, routing làm việc tốt hơn bridging trong những mạng lớn, và nó trở thành dạng chiếm lợi thế của việc tìm đường trên mạng Internet .
Các mạng nhỏ có thể có các bảng định tuyến được cấu hình thủ công, còn những mạng lớn hơn có topo mạng phức tạp và thay đổi liên tục thì xây dựng thủ công các bảng định tuyến là vô cùng khó khăn. Tuy nhiên, hầu hết mạng điện thoại chuyển mạch chung (public switched telephone network – PSTN) sử dụng bảng định tuyến được tính toán trước, với những tuyến dự trữ nếu các lộ trình trực tiếp đều bị nghẽn. Định tuyến động (dynamic routing) cố gắng giải quyết vấn đề này bằng việc xây dựng bảng định tuyến một cách tự động, dựa vào những thông tin được giao thức định tuyến cung cấp, và cho phép mạng hành động gần như tự trị trong việc ngăn chặn mạng bị lỗi và nghẽn.
Định tuyến động chiếm lợi thế trên Internet. Tuy nhiên, việc thông số kỹ thuật những giao thức định tuyến thường yên cầu nhiều kinh nghiệm tay nghề ; đừng nên nghĩ rằng kỹ thuật nối mạng đã tăng trưởng đến mức hoàn thành xong tự động hóa việc định tuyến. Cách tốt nhất là nên tích hợp giữa định tuyến bằng tay thủ công và tự động hóa .Những mạng trong đó những gói thông tin được luân chuyển, ví dụ như Internet, chia tài liệu thành những gói, rồi dán nhãn với những đích đến đơn cử và mỗi gói được lập lộ trình riêng không liên quan gì đến nhau. Các mạng xoay vòng, như mạng điện thoại thông minh, cũng thực thi định tuyến để tìm đường cho những vòng ( ví dụ như cuộc gọi điện thoại thông minh ) để chúng hoàn toàn có thể gửi lượng tài liệu lớn mà không phải liên tục lặp lại địa chỉ đích .Định tuyến IP truyền thống cuội nguồn vẫn còn tương đối đơn thuần vì nó dùng cách định tuyến bước sau đó ( next-hop routing ), router chỉ xem xét nó sẽ gửi gói thông tin đến đâu, và không chăm sóc đường đi sau đó của gói trên những bước truyền còn lại. Tuy nhiên, những kế hoạch định tuyến phức tạp hơn hoàn toàn có thể được, và thường được dùng trong những mạng lưới hệ thống như MPLS, ATM hay Frame Relay, những mạng lưới hệ thống này đôi lúc được sử dụng như công nghệ tiên tiến bên dưới để tương hỗ cho mạng IP .
Các kiểu định tuyến[sửa|sửa mã nguồn]
Thuật toán vector[sửa|sửa mã nguồn]
(distance-vector routing protocols)
Thuật toán này dùng thuật toán Bellman-Ford. Phương pháp này chỉ định một số lượng, gọi là ngân sách ( hay trọng số ), cho mỗi một link giữa những node trong mạng. Các node sẽ gửi thông tin từ điểm A đến điểm B qua đường đi mang lại tổng ngân sách thấp nhất ( là tổng những ngân sách của những liên kết giữa những node được dùng ) .Thuật toán hoạt động giải trí với những hành vi rất đơn thuần. Khi một node khởi động lần đầu, nó chỉ biết những node kề trực tiếp với nó, và ngân sách trực tiếp để đi đến đó ( thông tin này, list của những đích, tổng ngân sách của từng node, và bước sau đó để gửi tài liệu đến đó tạo nên bảng định tuyến, hay bảng khoảng cách ). Mỗi node, trong một tiến trình, gửi đến từng ” hàng xóm ” tổng ngân sách của nó để đi đến những đích mà nó biết. Các node ” hàng xóm ” nghiên cứu và phân tích thông tin này, và so sánh với những thông tin mà chúng đang ” biết ” ; bất kể điều gì cải tổ được những thông tin chúng đang có sẽ được đưa vào những bảng định tuyến của những ” hàng xóm ” này. Đến khi kết thúc, toàn bộ node trên mạng sẽ tìm ra bước truyền tiếp nối tối ưu đến tổng thể mọi đích, và tổng ngân sách tốt nhất .Khi một trong những node gặp yếu tố, những node khác có sử dụng node hỏng này trong lộ trình của mình sẽ vô hiệu những lộ trình đó, và tạo nên thông tin mới của bảng định tuyến. Sau đó chúng chuyển thông tin này đến tổng thể node gần kề và lặp lại quy trình trên. Cuối cùng, tổng thể node trên mạng nhận được thông tin update, và sau đó sẽ tìm đường đi mới đến toàn bộ những đích mà chúng còn tới được .
Thuật toán trạng thái liên kết[sửa|sửa mã nguồn]
(Link-state routing protocols)
Khi vận dụng những thuật toán trạng thái liên kết, mỗi node sử dụng tài liệu cơ sở của nó như thể một map của mạng với dạng một đồ thị. Để làm điều này, mỗi node phát đi tới tổng thể và toàn diện mạng những thông tin về những node khác mà nó hoàn toàn có thể liên kết được, và từng node góp thông tin một cách độc lập vào map. Sử dụng map này, mỗi router sau đó sẽ quyết định hành động về tuyến đường tốt nhất từ nó đến mọi node khác .Thuật toán đã làm theo cách này là Dijkstra, bằng cách kiến thiết xây dựng cấu trúc tài liệu khác, dạng cây, trong đó node hiện tại là gốc, và chứa mọi noded khác trong mạng. Bắt đầu với một cây khởi đầu chỉ chứa chính nó. Sau đó lần lượt từ tập những node chưa được thêm vào cây, nó sẽ thêm node có ngân sách thấp nhất để đến một node đã có trên cây. Tiếp tục quy trình đến khi mọi node đều được thêm .
Cây này sau đó phục vụ để xây dựng bảng định tuyến, đưa ra bước truyền kế tiếp tốt ưu, … để từ một node đến bất kỳ node khác trên mạng.
So sánh những thuật toán định tuyến[sửa|sửa mã nguồn]
Các giao thức định tuyến với thuật toán vector tỏ ra đơn thuần và hiệu suất cao trong những mạng nhỏ, và yên cầu ít ( nếu có ) sự giám sát. Tuy nhiên, chúng không làm việc tốt, và có tài nguyên tập hợp rất ít, dẫn đến sự tăng trưởng của những thuật toán trạng thái liên kết tuy phức tạp hơn nhưng tốt hơn để dùng trong những mạng lớn. Giao thức vector kém hơn với rắc rối về đếm đến vô tận .Ưu điểm chính của định tuyến bằng trạng thái liên kết là phản ứng nhạy bén hơn, và trong một khoảng chừng thời hạn hạn chế, so với sự biến hóa liên kết. Ngoài ra, những gói được gửi qua mạng trong định tuyến bằng trạng thái liên kết thì nhỏ hơn những gói dùng trong định tuyến bằng vector. Định tuyến bằng vector yên cầu bảng định tuyến không thiếu phải được truyền đi, trong khi định tuyến bằng trạng thái liên kết thì chỉ có thông tin về ” hàng xóm ” của node được truyền đi. Vì vậy, những gói này dùng tài nguyên mạng ở mức không đáng kể. Khuyết điểm chính của định tuyến bằng trạng thái liên kết là nó yên cầu nhiều sự tàng trữ và thống kê giám sát để chạy hơn định tuyến bằng vector .
Giao thức được định tuyến và giao thức định tuyến[sửa|sửa mã nguồn]
Sự nhầm lẫn thường xảy ra 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 )[sửa|sửa mã nguồn]
Một giao thức đã được định tuyến là bất kể một giao thức mạng nào phân phối rất đầy đủ thông tin trong địa chỉ tầng mạng của nó để cho phép một gói tin được truyền đi từ một sever ( host ) đến sever khác dựa trên sự sắp xếp về địa chỉ, không cần biết đến đường đi toàn diện và tổng thể từ nguồn đến đích. Giao thức đã được định tuyến định nghĩa khuôn dạng và mục tiêu của những trường có trong một gói. Các gói thường thì được luân chuyển từ mạng lưới hệ thống cuối đến một mạng lưới hệ thống cuối khác. Hầu như toàn bộ giao thức ở tầng 3 những giao thức khác ở những tầng trên đều hoàn toàn có thể được định tuyến, IP là một ví dụ. Nghĩa là gói tin đã được khuynh hướng ( có địa chỉ rõ ràng ) giống như lá thư đã được ghi địa chỉ rõ chỉ còn chờ routing ( tìm đường đi đến địa chỉ đó )Các giao thức ở tầng 2 như Ethernet là những giao thức không định tuyến được, vì chúng chỉ chứa địa chỉ tầng link, không đủ để định tuyến : một số ít giao thức ở tầng cao dựa trực tiếp vào đây mà không có thêm địa chỉ tầng mạng, như NetBIOS, cũng không định tuyến được .
Giao thức định tuyến ( routing protocols )[sửa|sửa mã nguồn]
Giao thức định tuyến được dùng trong khi thi hành thuật toán định tuyến để thuận tiện cho việc trao đổi thông tin giữa những mạng, được cho phép những router thiết kế xây dựng bảng định tuyến một cách linh động. Trong một số ít trường hợp, giao thức định tuyến hoàn toàn có thể tự chạy đè lên giao thức đã được định tuyến : ví dụ, BGP chạy đè trên TCP : cần quan tâm là trong quy trình thi hành mạng lưới hệ thống không tạo ra sự chịu ràng buộc giữa giao thức định tuyến và đã đượ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 )[sửa|sửa mã nguồn]
Một thông số kỹ thuật định tuyến gồm có bất kể giá trị nào được dùng bởi thuật toán định tuyến để xác lập một lộ trình có tốt hơn lộ trình khác hay không. Các thông số kỹ thuật hoàn toàn có thể là những thông tin như băng thông ( bandwidth ), độ trễ ( delay ), đếm bước truyền, ngân sách đường đi, trọng số, size tối đa gói tin ( MTU – Maximum transmission unit ), độ đáng tin cậy, và ngân sách tiếp thị quảng cáo. Bảng định tuyến chỉ tàng trữ những tuyến tốt nhất hoàn toàn có thể, trong khi cơ sở tài liệu trạng thái liên kết hay topo hoàn toàn có thể tàng trữ tổng thể những thông tin khác .Router dùng tính năng phân loại mức an toàn và đáng tin cậy ( administrative distance – AD ) để chọn đường đi tốt nhất khi nó ” biết ” hai hay nhiều đường để đến cùng một đích theo những giao thức khác nhau. AD định ra độ đáng 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 trong thứ tự độ đáng tin cậy từ cao đến thấp nhất có một giá trị AD. Một giao thức có giá trị AD thấp hơn thì được an toàn và đáng tin cậy hơn, ví dụ : OSPF có AD là 110 sẽ được chọn thay vì RIP có AD là 120 .Bảng sau đây cho biết sự sắp xếp mức đáng tin cậy được dùng trong những router Cisco
Giao thức
Administrative distance
Nối trực tiếp
0
Static route
1
EIGRP summary route
5
External BGP
20
Internal EIGRP
90
IGRP
100
OSPF
110
IS-IS
115
RIP
120
EGP
140
ODR
160
External EIGRP
170
Internal BGP
200
Không xác định
255
Các lớp giao thức định tuyến[sửa|sửa mã nguồn]
Dựa vào quan hệ của những dòng router với những mạng lưới 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 ở những 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)
