tailieunhanh - ĐỒ ÁN THIẾT KẾ CÔNG NGHỆ CHUYỂN MẠCH NHÃN ĐA GIAO THỨC, chương 11

Đị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. | 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 J 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 J 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 ưễ. .Để 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 sửa đổi danh sách nút ứng cử . Sau đó thuật toán lại được thực hiện lặp lại. Trong trường hợp tìm đường ngắn nhất từ một gốc đến tất cả các nút khác trong mạng thì thuật toán sẽ dừng khi nào danh sách các nút ứng cử là rỗng. Trong trường hợp tìm đường ngắn nhất từ một gốc đến một nút cụ thể thì thuật toán sẽ dừng lại khi nào nút đó được bổ sung vào cây đường ngắn nhất. Thuật toán SPF để tính toán xác định đường ngắn nhất từ nút SPF nguồn đến một số nút đích có thể được mô tả dưới dạng các bước như sau J Bước 1 khởi tạo Đặt danh sách các nút ứng cử bằng rỗng. Đặt cây đường ngắn nhất chỉ có gốc S. Đối với mỗi nút liền kề gốc đặt độ dài đường bằng độ dài kênh giữa gốc và nút. Đối với tất .