Tweet
3. Giải thuật chọn đường
Việc chọn đường cho một trung kế lưu lượng sử dụng trọng số quản trị (TE cost) của mỗi link riêng biệt. Trọng số quản trị này mặc nhiên là bằng metric IGP của link. Giải thuật chọn đường ràng buộc theo các bước sau:
– Cắt bỏ các link có resource-class bị loại do phép tính Affinity ra khỏi topology.
– Cắt bỏ các link không có đủ băng thông dự trữ theo yêu cầu của trung kế.
– Chạy giải thuật Dijktra để tìm ra đường có tổng TE-cost nhỏ nhất trên phần topology còn lại.
Sau khi thực hiện các bước trên mà vẫn còn nhiều đường ứng cử cho LSP (nhiều đường có cùng tổng TE metric) thì tiêu chuẩn thứ tự chọn lựa như sau:
– Đường có băng thông tối thiểu cao nhất.
– Đường có số hop nhỏ nhất.
– Chọn lựa ngẫu nhiên.
Khi đường LSP được tính xong, RSVP được dùng để dành trước băng thông thực sự, để phân phối các nhãn cho đường và hoàn thành việc thiết lập đường LSP.
Ví dụ về chọn đường cho trung kế lưu lượng:
Xét ví dụ chọn đường LSP cho một trung kế lưu lượng (tunnel) thiết lập giữa R1 (đầu nguồn) và R6 (đầu đích). Yêu cầu của trung kế lưu lượng như sau:
– Băng thông đòi hỏi ở mức ưu tiên 3 là 30 Mbps
– Các bit Affinity lớp tài nguyên là 0010 với mặt nạ là 0011, tức là chỉ thực hiện kiểm tra trên hai bit thấp.
Link R4-R3 cần được loại trừ khỏi đường LSP, do vậy chuỗi bit resource-class của link này sẽ được đặt là 0011. Khi các bit Affinity lớp tài nguyên của trung kế lưu lượng được so sánh với các bit resource-class là không trùng nên link R4-R3 bị loại.
Tham số tiếp theo được kiểm tra trong quá trình tính toán đường ràng buộc là TE cost (trọng số quản trị) của mỗi link mà đường hầm khả năng đi qua. Nếu không xét tài nguyên thì đường R1-R4-R6 có tổng cost thấp nhất là 30. Tất cả các đường khả thi khác đều có tổng cost cao hơn.
Khi tài nguyên được đưa vào tính toán, thấy rằng trên đường ngắn nhất không có đủ băng thông thỏa mãn các đòi hỏi của trung kế lưu lượng (đòi hỏi 30 Mbps trong khi chỉ có 20 Mbps khả dụng). Kết quả là link R4-R6 cũng bị loại khỏi phép tính đường LSP.
Sau khi loại bỏ các link không thỏa mãn các đòi hỏi của trung kế lưu lượng, kết quả có hai đường LSP là: R1-R2-R3-R6 và R1-R5-R6. Cả hai đường đều có tổng cost là 40, để chọn một đường phải giải quyết bằng luật “tie-break”.
Trước tiên, băng thông tối thiểu trên đường được so sánh. Sau khi so sánh, vẫn còn cả hai đường vì chúng đều cung cấp ít nhất 50 Mbps băng thông. Tiếp theo, luật số hop nhỏ nhất trên đường LSP được áp dụng. Vì đường R1-R5-R6 có hop-count nhỏ hơn nên cuối cùng nó được chọn và quá trình tính toán ràng buộc kết thúc.
Việc chọn đường cho một trung kế lưu lượng sử dụng trọng số quản trị (TE cost) của mỗi link riêng biệt. Trọng số quản trị này mặc nhiên là bằng metric IGP của link. Giải thuật chọn đường ràng buộc theo các bước sau:
– Cắt bỏ các link có resource-class bị loại do phép tính Affinity ra khỏi topology.
– Cắt bỏ các link không có đủ băng thông dự trữ theo yêu cầu của trung kế.
– Chạy giải thuật Dijktra để tìm ra đường có tổng TE-cost nhỏ nhất trên phần topology còn lại.
Sau khi thực hiện các bước trên mà vẫn còn nhiều đường ứng cử cho LSP (nhiều đường có cùng tổng TE metric) thì tiêu chuẩn thứ tự chọn lựa như sau:
– Đường có băng thông tối thiểu cao nhất.
– Đường có số hop nhỏ nhất.
– Chọn lựa ngẫu nhiên.
Khi đường LSP được tính xong, RSVP được dùng để dành trước băng thông thực sự, để phân phối các nhãn cho đường và hoàn thành việc thiết lập đường LSP.
Ví dụ về chọn đường cho trung kế lưu lượng:
Xét ví dụ chọn đường LSP cho một trung kế lưu lượng (tunnel) thiết lập giữa R1 (đầu nguồn) và R6 (đầu đích). Yêu cầu của trung kế lưu lượng như sau:
– Băng thông đòi hỏi ở mức ưu tiên 3 là 30 Mbps
– Các bit Affinity lớp tài nguyên là 0010 với mặt nạ là 0011, tức là chỉ thực hiện kiểm tra trên hai bit thấp.
Link R4-R3 cần được loại trừ khỏi đường LSP, do vậy chuỗi bit resource-class của link này sẽ được đặt là 0011. Khi các bit Affinity lớp tài nguyên của trung kế lưu lượng được so sánh với các bit resource-class là không trùng nên link R4-R3 bị loại.
Xem xét các ràng buộc khống chế
Tham số tiếp theo được kiểm tra trong quá trình tính toán đường ràng buộc là TE cost (trọng số quản trị) của mỗi link mà đường hầm khả năng đi qua. Nếu không xét tài nguyên thì đường R1-R4-R6 có tổng cost thấp nhất là 30. Tất cả các đường khả thi khác đều có tổng cost cao hơn.
Khi tài nguyên được đưa vào tính toán, thấy rằng trên đường ngắn nhất không có đủ băng thông thỏa mãn các đòi hỏi của trung kế lưu lượng (đòi hỏi 30 Mbps trong khi chỉ có 20 Mbps khả dụng). Kết quả là link R4-R6 cũng bị loại khỏi phép tính đường LSP.
Xem xét tài nguyên khả dụng
Sau khi loại bỏ các link không thỏa mãn các đòi hỏi của trung kế lưu lượng, kết quả có hai đường LSP là: R1-R2-R3-R6 và R1-R5-R6. Cả hai đường đều có tổng cost là 40, để chọn một đường phải giải quyết bằng luật “tie-break”.
Trước tiên, băng thông tối thiểu trên đường được so sánh. Sau khi so sánh, vẫn còn cả hai đường vì chúng đều cung cấp ít nhất 50 Mbps băng thông. Tiếp theo, luật số hop nhỏ nhất trên đường LSP được áp dụng. Vì đường R1-R5-R6 có hop-count nhỏ hơn nên cuối cùng nó được chọn và quá trình tính toán ràng buộc kết thúc.
Chọn đường tốt nhất
Lê Huy – VnPro