Tài liệu ĐỒ ÁN THIẾT KẾ CÔNG NGHỆ CHUYỂN MẠCH NHÃN ĐA GIAO THỨC, chương 11 pdf

chương 11 : Thuật toán định tuyến

cưỡng bức

Định tuyến cưỡng bức phải tính toán xác định đường đi thoả

mãn các điều kiện sau:

Tối ưu theo một tiêu chuẩn nào đó (ví dụ đường ngắn nhất

hoặc số chặng ít nhất)

Thoả mãn các điều kiện ràng buộc.

Thuật toán “đường ngắn nhất đầu tiên” (SPF) thường được

sử dụng để tìm đường tối ưu theo tiêu chuẩn nào đó. Các mạng IP

truyền thống sử dụng thuật toán này để tìm đường tối ưu theo tiêu

chuẩn nào đó (chẳng hạn: số hop…) mà không tính tới các yếu tố

bổ sung như trễ, biến thiên trễ…Để thoả mãn cả các điều kiện ràng

buộc thì thuật toán SPF cần phải thay đổi để bao gồm các điều kiện

ràng buộc. Thuật toán mới này gọi là SPF cưỡng bức (CSPF).

Trước hết chúng ta tìm hiểu hoạt đông của thuật toán SPF.

Thuật toán SPF hoạt động khởi đầu tại một nút được gọi là gốc và

bắt đầu tính toán xây đường ngắn nhất ứng với gốc là nút đó. Tại

mỗi vòng của thuật toán sẽ có một danh sách các nút “ứng cử”

không nhất thiết phải là ngắn nhất. Tuy nhiên ứng với nút “ứng cử”

ở ngay kề nút gốc thì đường nối tới nút này phải là ngắn nhất. Vì

vậy tại mỗi vòng, thuật toán sẽ tách nút có đường ngắn nhất tới nút

gốc từ danh sách nút “ứng cử”. Nút này sẽ được bổ sung vào cây

đường ngắn nhất, thì các nút không nằm trên cây đường ngắn nhất

nhưng liền kề ngay nút này cũng được kiểm tra để bổ sung hoặc