Tweet
Tác giả:
Trần Thị Tố Uyên
Trần Thị Tố Uyên
THUẬT TOÁN CSPF (CONSTRAINED SHORTED PATH FIRST)
1. Hoạt động của CSPF:
- Có hai điểm khác biệt đáng quan tâm giữa SPF bình thường do các giao thức định tuyến thực hiện và CSPF của MPLS TE:
- Thứ nhất, tiến trình thiết lập tuyến không được thiết kế để tìm ra đường đi tốt nhất đến mọi bộ định tuyến mà chỉ đến điểm cuối đường hầm (tunnel endpoint).
- Thứ hai, thay vì chỉ quan tâm đến một loại chi phí trên kết nối giữa hai láng giềng còn phải quan tâm đến:
- Băng thông (bandwidth)
- Các thuộc tính kết nối (link attributes)
- Trọng số quản trị (Administrative weight)
- Các thuộc tính kết nối (link attributes)
- Trọng số quản trị (Administrative weight)
- Các bước thực hiện thuật toán CSPF như sau:
- Bước 1: Một nút tự đưa thông tin của chính mình vào danh sách PATH với cost = 0, next hop là chính nó và thiết lập băng thông = N/A.
- Bước 2: Xem xét nút vừa vào danh sách PATH, và gọi nó là nút PATH. Kiểm tra danh sách các nút láng giềng của nó. Thêm mỗi láng giềng vào danh sách TENT với một next hop của nút PATH, trừ khi nút láng giềng đã có có danh sách TENT hoặc PATH với chi phí thấp hơn. Không thêm đường đi này vào TENT trừ khi nó được cấu hình ràng buộc cho đường hầm – băng thông (bandwidth) và quan hệ (affinity). Nếu nút vừa được thêm vào danh sách TENT đã có trong danh sách, nhưng với một chi phí cao hơn hoặc thấp hơn băng thông tối thiểu, thay thế đường đi có chi phí cao hơn bằng đường hiện tại.
- Bước 3: Tìm láng giềng trong danh sách TENT với chi phí thấp hơn, thêm láng giềng đó vào danh sách PATH, và lặp lại bước 2. Nếu TENT rỗng hoặc trên PATH còn lại nút ở cuối đường hầm thì dừng.
- Dễ thấy, đường đi tốt nhất từ bộ định tuyến A đến bộ định tuyến D là A->B->C->D, với tổng chi phí bằng 12. Nhưng không thỏa băng thông có sẵn bằng 60 Mbps. CSPF cần tính lại đường đi ngắn nhất với băng thông có sẵn 60 Mbps.
- Trong thực tế việc tính toán phức tạp hơn nhiều. CSPF phải lưu giữ mọi nút trên đường đi, không chỉ là nút kế tiếp. Cũng như, không chỉ quan tâm đến băng thông mà còn xem xét đến các thuộc tính kết nối và các phương pháp quyết định (tiebreakers).
2. Các phương pháp quyết định trong CSPF (Tiebreakers in CSPF):
- SPF thông thường (dùng trong OSPF, IS-IS) có thể sử dụng nhiều đường đi đến đích có cùng chi phí. Điều này thỉnh thoảng được gọi là Nhiều đường đi cùng chi phí (ECMP – Equal-Cost MultiPath), và nó rất hữu dụng trong giao thức định tuyến nội (IGP – Interior Gateway Protocol).
- Tuy nhiên trong CSPF, không được tính mọi đường đi tốt nhất đến mọi đích có thể. Bạn phải tìm một đường đi đến một đích. Bạn sẽ làm gì khi đặt một nút vào TENT và nút đó đã có trong TENT với cùng chi phí? Bạn cần tìm ra một cách để phân biệt các đường đi với nhau.
- Đây là các phương pháp quyết định đường đi có cùng chi phí:
1. Chọn đường đi có băng thông có sẵn tối thiểu rộng nhất.
2. Nếu vẫn chưa được, chọn đường đi có hop count thấp nhất (số lượng bộ định tuyến trong đường đi).
3. Nếu vẫn chưa thõa, chọn đường đi ngẫu nhiên.
2. Nếu vẫn chưa được, chọn đường đi có hop count thấp nhất (số lượng bộ định tuyến trong đường đi).
3. Nếu vẫn chưa thõa, chọn đường đi ngẫu nhiên.
Ghi chú:
- Mọi thứ không thực sự là “ngẫu nhiên”. Khi xem xét xa hơn trong quá trình quyết định, bạn chọn đường đi trên cùng (top path) trong PATH. Không “ngẫu nhiên” khi mọi đường đi có thể có một cơ hội được lựa chọn, nhưng chọn ngẫu nhiên với đường đi cuối cùng của PATH có cấu trúc độc lập và được thực thi độc lập. - Các phương pháp này đưa ra cho một nút trong TENT. Tại một thời điểm nào đó, một nút chỉ nên được liệt kê một lần trong TENT. Đây là sự khác biệt với IGP SPF – có thể chọn nhiều đường cho một nút và chia tải giữa chúng.
Comment