14.Định tuyến là một tiến trình lựa chọn đường đi cho thực thể thông tin chuyển qua mạng. Định tuyến cung cấp các phương tiện tìm kiếm các tuyến đường theo thông tin mà thực thể thông tin được chuyển giao trên mạng.Một Node trên mạng nhận gói trên một đường vào (incoming link) rồi chuyển tiếp nó tới một đường ra (outgoing link) Hướng tới đích của data.Mục tiêu của định tuyến là sử dụng tối ưu tài nguyên mạng, vì vậy nó phải dựa vào các tham số mạng và người sử dụng như:Xác suất nghẽn,băng thông,độ trễ ,độ tin cậy,giá thành.................

+Một kĩ thuật định tuyến phải thực hiện tốt 2 chức năng sau:

_ Quyết định chọn đường đi theo những tiêu chuẩn nào (một hoặc một vài tiêu chuẩn trên).

_ Cập nhật thông tin định tuyến, tức là thông tin dùng cho chức năng 1.

Trong các mạng máy tính có rất nhiều các kỹ thuật định tuyến khác nhau đã được

đưa ra. Sự phân biệt giữa các kỹ thuật định tuyến chủ yếu căn cứ vào các yếu tố liên

quan đến 2 chức năng chính đã chỉ ra trên đây. Các yếu tố đó thường là:

(a) Sự phân tán của các chức năng chọn đường trên các nút của mạng.

(b) Sự thích nghi với trạng thái hiện hành của mạng.

(c) Các tiêu chuẩn tối ưu để định tuyến.

Dựa trên yếu tố (a) ta có thể phân biệt kỹ thuật định tuyến thành: kỹ thuật định

tuyến tập trung và phân tán. Dựa trên yếu tố (b) ta có kỹ thuật định tuyến tĩnh hoặc

động (tương thích). Cuối cùng các kỹ thuật định tuyến cùng loại theo (a) và (b) lại có

thể phân biệt bởi yếu tố (c). Một số tiêu chí cơ bản nhằm xác định kỹ thuật định tuyến

trong thực tế có thể là:

_Độ trễ trung bình của thời gian truyền gói tin.

_Số lượng nút trung gian giữa nguồn và đích của gói tin.

_Độ an toàn của việc truyền tin.

_Nguồn tài nguyên mạng sử dụng cho truyền tin . v.v..

_Tổ hợp của các tiêu chuẩn trên.

* Các giao thức định tuyến:

+Kỹ thuật định tuyến trong mạng ATM

Hoạt động định tuyến trong mạng ATM là một thành phần của giao diện mạng-mạng riêng PNNI (Private Network Network Interface). PNNI là là tổ hợp của kỹ thuật

định tuyến và báo hiệu dựa trên trạng thái liên kết được sử dụng trong mạng chuyển

mạch ATM

+Giao thức định tuyến trong mạng IP

Khái niệm miền hay hệ thống tự trị xuất phát từ mạng Internet. Từ khía cạnh định

tuyến, mạng Internet là mạng diện rộng lớn đến mức một giao thức định tuyến không

thể xử lý công việc cập nhật các bảng định tuyến của tất cả các bộ định tuyến. Vì lý do

này, liên mạng được chia thành nhiều hệ thống tự trị AS (Autonomous System). Hệ

thống tự trị là một nhóm các mạng và bộ định tuyến có chung chính sách quản trị, đôi

khi còn được gọi là miền định tuyến. Các giao thức định tuyến được sử dụng bên trong

một AS được gọi là giao thức định tuyến nội miền IGP (Interior Gateway Protocol).

+thuật toán Bellman-Ford:thuật toán Bellman-Ford  tính toán đường dẫn ngắn nhất tới một node đích trong một khoảng thời gian. Thuật  toán  sử  dụng  node  trung  gian  k;  thuật  toán Bellman-Ford  coi node k là chung cho tất cả các node để tìm bước nhảy kế tiếp tốt nhất tới node j.

Sử dụng một cấu trúc cơ sở dữ liệu tốt. Chú ý rằng nếu mạng được kết nối theo hình lưới đầy đủ thì số lượng liên kết song hướng là  N(N-1)/2

+Thuật toán Dijktra:Dijkstra tính toán đường dẫn ngắn nhất tới tất cả các node đích (đôi khi gọi là cây đường dẫn ngắn nhất). Thuật toán  Dijkstra là node trung gian được lựa chọn đầu tiên và cố định và vì vậy tính toán đường dẫn tới tất cả các node j chưa được thực hiện ngay. Độ phức tạp tính toán của thuật toán Dijkstra là O(N2).