Tweet
1. Giới thiệu
Thuật toán tìm đường đi ngắn nhất có ràng buộc (CSPF – Constrained SPF) tính đường đi ngắn nhất dựa vào việc quản lý metric. CSPF chỉ quan tâm tới các đường mà thỏa mãn một trong các điền kiện ràng buộc (như băng thông sẵn có) bằng cách loại bớt các liên kết không thỏa.
Khi điều kiện ràng buộc về “màu liên kết” (còn gọi là một thuộc tính quản lý, thường mang tính trực giác), các liên kết sẽ được cấu hình với những màu khác nhau và một liên kết có thể có nhiều màu hay không có màu nào hết, tối đa có 32 màu được dùng. Việc quy định màu cho liên kết thường dựa trên các thuộc tính như độ trễ, độ mất gói, giá trị phí tổn hay vị trí địa lý. Các màu ở đây cho biết được LSP sẽ chứa hay không chứa liên kết nào của một tuyến cụ thể. Ví dụ, nếu gán các liên kết có độ trễ cao với màu “xanh lam”, ta có thể tính được đường truyền mà không qua liên kết đó bằng cách loại bỏ các liên kết “xanh lam” khỏi đường truyền đó. Theo thuật toán CSPF, các liên kết có màu không thích hợp với các điều kiện ràng buộc sẽ bị loại khỏi mô hình.
Giống như SPF, kết quả thu được của thuật toán CSPF là một đường truyền đơn. Nếu tại cùng một thời điểm có các đường đi đều tốt như nhau thì chỉ có một đường là được chọn. Các phương pháp quyết định chọn đường đi trong CSPF gồm có: chọn ngẫu nhiên, chọn theo least fill (liên kết còn trống) hay most-fill (liên kết đã đầy).
Dù sự tính toán đường truyền diễn ra như thế nào thì một bộ chuyển mạch nhãn chuyển tiếp trạng thái cũng phải được thiết lập dọc theo đường truyền để bảo đảm rằng lưu lượng không bị phân tán khỏi đường truyền mong muốn.
2. 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ũng giống như qui trình tính toán của thuật toán SPF truyền thống, trong qui trình tính toán của thuật toán CSPF, các nút duy trì hai danh sách PATH và TENT sau đây:
• Danh sách PATH, lưu trữ nút mà từ đó có thể tới được mỗi mạng đích, danh sách này chứa được tất cả các đường dẫn tối ưu nhất tới các mạng đích.
• Danh sách TENT, lưu trữ các nút mà từ đó có thể tới được mỗi mạng đích nhưng chúng có thể không phải là đường dẫn tối ưu nhất tới các mạng đích đó.
• Bốn thuộc tính được thể hiện trong danh sách PATH/TENT: link, cost, next hop, available bandwidth.
6. 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út này 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 nút lân cận vào TENT List trước khi nút này có các thuộc tính ràng buộc thỏa mãn tất cả các thuộc tính ràng buộc yêu cầu bởi trung kế lưu lượng. Nếu nút được thêm vào danh sách TENT đã tồn tại trong danh sách này nhưng với giá trị Cost cao hơn hoặc các giá trị ràng buộc ít hơn thì thay thế các giá trị cũ bằng các giá trị mới tối ưu hơn.
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.
4. Các phương pháp quyết định trong CSPF
SPF (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à 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, chỉ dùng một đường đi tốt nhất đến một đích. Nên khi đặt một nút mạng vào TENT List và nút đó có trong TENT List với cùng chi phí cần có một phương pháp phân biệt các đường đi với nhau.
Phương pháp quyết định đường đi có cùng chi phí:
• Chọn đường đi có băng thông khả dụng hiện thời lớn nhất.
• Chọn đường đi có hop count thấp nhất .
• Nếu vẫn chưa thỏa, chọn đường đi ngẫu nhiên.
5. Minh họa trực quan cho thuật toán tìm đường CSPF
Ta xét một ví dụ về tính toán đường dẫn LSP ràng buộc cho một trung kế lưu lượng thiết lập giữa R1 trong vai trò Headend-LSR và R6 trong vai trò Tailend-LSR như hình dưới:
R1 thiết lập một đường dẫn ràng buộc tới R6 cho các lưu lượng của trung kế lưu lượng có yêu cầu là:
• Trung kế có băng thông tối thiểu đòi hỏi là 80Mbps.
• Trung kế có độ ưu tiên thiết lập là 3, độ ưu tiên giữ là 2.
• Trung kế yêu cầu Affinity = 0010 và mặt nạ Mask = 0011 (kiểm tra hai bit thấp và yêu cầu hai bit này bắt buộc phải có giá trị lần lượt là ‘ 1 ’ và ‘0’).
Các liên kết trong mạng có chi phí IGP Cost và thuộc tính ràng buộc về băng thông khả dụng hiện thời trong hình vẽ với định dạng là (TE Metric, Unreserved Bandwidth, Attribute Flags).
Bước đầu tiên, thuật toán CSPF thực hiện quá trình tính toán và loại bỏ các đường dẫn có tập các liên kết có thuộc tính ràng buộc không thỏa mãn yêu cầu của trung kế lưu lượng như sau:
• Liên kết R4-R6 bị loại bỏ do thuộc tính ràng buộc Unreserved Bandwidth = 70Mbps không thỏa mãn yêu cầu 80Mbps của trung kế lưu lượng.
• Liên kết R4-R3 bị loại bỏ do thuộc tính ràng buộc Attribute Flags = 1011 không thỏa mãn yêu cầu các bit ‘ 1 ’ ‘0’ ở vị trí hai bit thấp của trung kế lưu lượng.
Loại bỏ những đường dẫn không thõa mãn thuộc tính ràng buộc:
Bước tiếp theo, thuật toán CSPF tiếp tục tính toán và xem xét đến giá trị TE Metric, chọn ra đường dẫn có TE Metric tổng hợp nhỏ nhất (theo mặc định thì giá trị TE Metric = IGP Cost):
• Đường dẫn Rl->R2->R3->R6 có TE Metric = 70
• Đường dẫn Rl->R4->R3->R6 có TE Metric = 60, nhưng đã bị loại bỏ từ bước đầu tiên do không thỏa mãn các thuộc tính ràng buộc
• Đường dẫn Rl->R4->R6 có TE Metric = 55, nhưng đã bị loại bỏ từ bước đầu tiên do không thỏa mãn các thuộc tính ràng buộc
• Đường dẫn R1 ->R5->R6 có TE Metric = 70
Có thể nhận thấy đường dẫn Rl->R4->R6 có TE Metric nhỏ nhất (55) nhưng sẽ không trở thành đường dẫn cho lưu lượng của trung kế lưu lượng do không thỏa mãn các thuộc tính ràng buộc. Tương tự với đường dẫn Rl->R4->R3->R6. Và chỉ còn lại hai đường dẫn là Rl->R2->R3->R6 và Rl->R5->R6 đều có TE Metric = 70 và đều thỏa mãn các thuộc tính ràng buộc. Do vậy cần sử dụng các tiêu chuẩn “tie-breaker” để lựa chọn ra một đường dẫn cho trung kế lưu lượng. Tiêu chuẩn về băng thông khả dụng hiện thời lớn nhất không phù hợp vì cả hai đường đều có băng thông khả dụng hiện thời 50Mbps. Tuy nhiên đường dẫn Rl->R5->R6 được chọn lựa vì theo tiêu chuẩn tiếp theo thì đường dẫn có số chặng ít nhất sẽ được chọn.
Đến đây quá trình tính toán chọn đường của thuật toán CSPF dành cho các lưu lượng của trung kế lưu lượng kết thúc.
Thuật toán tìm đường đi ngắn nhất có ràng buộc (CSPF – Constrained SPF) tính đường đi ngắn nhất dựa vào việc quản lý metric. CSPF chỉ quan tâm tới các đường mà thỏa mãn một trong các điền kiện ràng buộc (như băng thông sẵn có) bằng cách loại bớt các liên kết không thỏa.
Khi điều kiện ràng buộc về “màu liên kết” (còn gọi là một thuộc tính quản lý, thường mang tính trực giác), các liên kết sẽ được cấu hình với những màu khác nhau và một liên kết có thể có nhiều màu hay không có màu nào hết, tối đa có 32 màu được dùng. Việc quy định màu cho liên kết thường dựa trên các thuộc tính như độ trễ, độ mất gói, giá trị phí tổn hay vị trí địa lý. Các màu ở đây cho biết được LSP sẽ chứa hay không chứa liên kết nào của một tuyến cụ thể. Ví dụ, nếu gán các liên kết có độ trễ cao với màu “xanh lam”, ta có thể tính được đường truyền mà không qua liên kết đó bằng cách loại bỏ các liên kết “xanh lam” khỏi đường truyền đó. Theo thuật toán CSPF, các liên kết có màu không thích hợp với các điều kiện ràng buộc sẽ bị loại khỏi mô hình.
Giống như SPF, kết quả thu được của thuật toán CSPF là một đường truyền đơn. Nếu tại cùng một thời điểm có các đường đi đều tốt như nhau thì chỉ có một đường là được chọn. Các phương pháp quyết định chọn đường đi trong CSPF gồm có: chọn ngẫu nhiên, chọn theo least fill (liên kết còn trống) hay most-fill (liên kết đã đầy).
Dù sự tính toán đường truyền diễn ra như thế nào thì một bộ chuyển mạch nhãn chuyển tiếp trạng thái cũng phải được thiết lập dọc theo đường truyền để bảo đảm rằng lưu lượng không bị phân tán khỏi đường truyền mong muốn.
2. 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ũng giống như qui trình tính toán của thuật toán SPF truyền thống, trong qui trình tính toán của thuật toán CSPF, các nút duy trì hai danh sách PATH và TENT sau đây:
• Danh sách PATH, lưu trữ nút mà từ đó có thể tới được mỗi mạng đích, danh sách này chứa được tất cả các đường dẫn tối ưu nhất tới các mạng đích.
• Danh sách TENT, lưu trữ các nút mà từ đó có thể tới được mỗi mạng đích nhưng chúng có thể không phải là đường dẫn tối ưu nhất tới các mạng đích đó.
• Bốn thuộc tính được thể hiện trong danh sách PATH/TENT: link, cost, next hop, available bandwidth.
6. 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út này 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 nút lân cận vào TENT List trước khi nút này có các thuộc tính ràng buộc thỏa mãn tất cả các thuộc tính ràng buộc yêu cầu bởi trung kế lưu lượng. Nếu nút được thêm vào danh sách TENT đã tồn tại trong danh sách này nhưng với giá trị Cost cao hơn hoặc các giá trị ràng buộc ít hơn thì thay thế các giá trị cũ bằng các giá trị mới tối ưu hơn.
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.
4. Các phương pháp quyết định trong CSPF
SPF (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à 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, chỉ dùng một đường đi tốt nhất đến một đích. Nên khi đặt một nút mạng vào TENT List và nút đó có trong TENT List với cùng chi phí cần có một phương pháp phân biệt các đường đi với nhau.
Phương pháp quyết định đường đi có cùng chi phí:
• Chọn đường đi có băng thông khả dụng hiện thời lớn nhất.
• Chọn đường đi có hop count thấp nhất .
• Nếu vẫn chưa thỏa, chọn đường đi ngẫu nhiên.
5. Minh họa trực quan cho thuật toán tìm đường CSPF
Ta xét một ví dụ về tính toán đường dẫn LSP ràng buộc cho một trung kế lưu lượng thiết lập giữa R1 trong vai trò Headend-LSR và R6 trong vai trò Tailend-LSR như hình dưới:
R1 thiết lập một đường dẫn ràng buộc tới R6 cho các lưu lượng của trung kế lưu lượng có yêu cầu là:
• Trung kế có băng thông tối thiểu đòi hỏi là 80Mbps.
• Trung kế có độ ưu tiên thiết lập là 3, độ ưu tiên giữ là 2.
• Trung kế yêu cầu Affinity = 0010 và mặt nạ Mask = 0011 (kiểm tra hai bit thấp và yêu cầu hai bit này bắt buộc phải có giá trị lần lượt là ‘ 1 ’ và ‘0’).
Các liên kết trong mạng có chi phí IGP Cost và thuộc tính ràng buộc về băng thông khả dụng hiện thời trong hình vẽ với định dạng là (TE Metric, Unreserved Bandwidth, Attribute Flags).
Bước đầu tiên, thuật toán CSPF thực hiện quá trình tính toán và loại bỏ các đường dẫn có tập các liên kết có thuộc tính ràng buộc không thỏa mãn yêu cầu của trung kế lưu lượng như sau:
Mô hình dùng thuật toán tìm đường CSPF
• Liên kết R4-R6 bị loại bỏ do thuộc tính ràng buộc Unreserved Bandwidth = 70Mbps không thỏa mãn yêu cầu 80Mbps của trung kế lưu lượng.
• Liên kết R4-R3 bị loại bỏ do thuộc tính ràng buộc Attribute Flags = 1011 không thỏa mãn yêu cầu các bit ‘ 1 ’ ‘0’ ở vị trí hai bit thấp của trung kế lưu lượng.
Loại bỏ những đường dẫn không thõa mãn thuộc tính ràng buộc:
Loại bỏ link không thỏa mãn thuộc tính ràng buộc
Bước tiếp theo, thuật toán CSPF tiếp tục tính toán và xem xét đến giá trị TE Metric, chọn ra đường dẫn có TE Metric tổng hợp nhỏ nhất (theo mặc định thì giá trị TE Metric = IGP Cost):
• Đường dẫn Rl->R2->R3->R6 có TE Metric = 70
• Đường dẫn Rl->R4->R3->R6 có TE Metric = 60, nhưng đã bị loại bỏ từ bước đầu tiên do không thỏa mãn các thuộc tính ràng buộc
• Đường dẫn Rl->R4->R6 có TE Metric = 55, nhưng đã bị loại bỏ từ bước đầu tiên do không thỏa mãn các thuộc tính ràng buộc
• Đường dẫn R1 ->R5->R6 có TE Metric = 70
Có thể nhận thấy đường dẫn Rl->R4->R6 có TE Metric nhỏ nhất (55) nhưng sẽ không trở thành đường dẫn cho lưu lượng của trung kế lưu lượng do không thỏa mãn các thuộc tính ràng buộc. Tương tự với đường dẫn Rl->R4->R3->R6. Và chỉ còn lại hai đường dẫn là Rl->R2->R3->R6 và Rl->R5->R6 đều có TE Metric = 70 và đều thỏa mãn các thuộc tính ràng buộc. Do vậy cần sử dụng các tiêu chuẩn “tie-breaker” để lựa chọn ra một đường dẫn cho trung kế lưu lượng. Tiêu chuẩn về băng thông khả dụng hiện thời lớn nhất không phù hợp vì cả hai đường đều có băng thông khả dụng hiện thời 50Mbps. Tuy nhiên đường dẫn Rl->R5->R6 được chọn lựa vì theo tiêu chuẩn tiếp theo thì đường dẫn có số chặng ít nhất sẽ được chọn.
Đến đây quá trình tính toán chọn đường của thuật toán CSPF dành cho các lưu lượng của trung kế lưu lượng kết thúc.
Lê Huy – VnPro