ĐỒ Á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...
Nội dung trích xuất từ tài liệu:
ĐỒ ÁN THIẾT KẾ CÔNG NGHỆ CHUYỂN MẠCH NHÃN ĐA GIAO THỨC, chương 11 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 đượcsử dụng để tìm đường tối ưu theo tiêu chuẩn nào đó. Các mạng IPtruyền thống sử dụng thuật toán này để tìm đường tối ưu theo tiêuchuẩ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àngbuộc thì thuật toán SPF cần phải thay đổi để bao gồm các điều kiệnrà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ạimỗ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útgố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ấtnhưng liền kề ngay nút này cũng được kiểm tra để bổ sung hoặcsửa đổi danh sách nút “ứng cử”. Sau đó thuật toán lại được thựchiện lặp lại. Trong trường hợp tìm đường ngắn nhất từ một gốc đếntất cả các nút khác trong mạng thì thuật toán sẽ dừng khi nào danhsách các nút “ứng cử” là rỗng. Trong trường hợp tìm đường ngắnnhất từ một gốc đến một nút cụ thể thì thuật toán sẽ dừng lại khinà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ộtsố nút (đích) có thể được mô tả dưới dạng các bước như sau:  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 cả các nút khác, đặt độ dài này bằng vô cùng.  Bước 2: Đặt tên nút bổ sung vào cây đường ngắn nhất là V. Đối với mỗi kênh nối vào nút này, kiểm tra các nút phía còn lại của kênh. Đánh dấu các nút này là W. Bước 2a: Nếu như nút W này đã có trong danh sách cây đường ngắn nhất thì kiểm tra tiếp với các kênh còn laị nối với nút V. Bước 2b: Trong trường hợp ngược lại (W không nằm trong danh sách cây đường ngắn nhất) thì tính độ dài của đường nối từ gốc đến nút W ( độ dài này bằng tổng độ dài của đường nối từ gốc đến nút V cộng với độ dài từ nút V đến nút W). Nếu như W không nằm trong danh sách các nút “ứng cử” thì giá trị độ dài đường hiện thời lớn hơn giá trị độ dài đường mới tính và gán giá trị độ dài đường từ gốc đến nút W bằng độ dài mới tính.  Bước 3: Trong danh sách nút “ứng cử”, tìm một nút với độ dài đường ngắn nhất. Bổ sung nút này vào cây đường ngắn nhất và xoá nút này khỏi danh sách nút “ứng cử”. Nếu nút này là nút D thì thuật toán kết thúc và ta được cây đường ngắn nhất từ nút nguồn SPF đến nút đích D. Nếu như nút này chưa phải là nút D thì quay trở lại bước 2. Từ các bước của thuật toán SPF đơn giản trên đây, chúng tadễ dàng sửa đổi nó trở thành CSPF. Tất cả chúng ta phải làm đó làsửa đổi bước thực hiện bổ sung sửa đổi danh sách nút “ứng cử”.Cụ thể là bước 2, khi chúng ta kiểm tra các kênh nối với nút V, đốivới mỗi kênh trước hết chúng ta kiểm tra xem kênh đó có thoả mãnđiều kiện ràng buộc không? Chỉ khi điều kiện này được thoả mãn,sau đó chúng ta mới kiểm tra nút W ở đầu kia của kênh. Thôngthường chúng ta hay gặp bài toán tìm đường từ S đến D thoả mãnmột số điều kiện ràng buộc là C1, C2,…, Cn, khi đó tại bước 2chúng ta sẽ kiểm tra tất cả các kênh nối với nút V, đối với mỗikênh trước hết chúng ta kiểm tra xem nó có thoả mãn điều kiện C1,C2,.., Cn. Chỉ khi kênh thoả mãn tất cả các điều kiện ràng buộc thìchúng ta mới kiểm tra nút W ở phía đầu kia của kênh. Về tổng quát, thủ tục kiểm tra xem kênh có thoả mãn mộtđiều kiện ràng buộc cụ thể là đặc điểm của định tuyến cưỡng bức.Ví dụ như nếu điều kiện ràng buộc cần thoả mãn là độ rộng băngtần khả dụng, khi đó chúng ta cần kiểm tra độ rộng băng tần khảdụng của kênh có lớn hơn một giá trị độ rộng băng tần được chỉ ratrong điều kiện ràng buộc; chỉ khi thoả mãn chúng ta mới kiểm tranút W ở đầu kia của kênh. Để kiểm tra kênh có thoả mãn một điều kiện ràng buộc cụ thểnào đó thì chúng ta phải biết trước các thông tin của kênh tươngứng có liên quan đến điều kiện ràng buộc. Ví dụ như khi điều kiệnràng buộc cần thoả mãn là độ rộng băng tần khả dụng thì thông tincần có là độ ...