Giải thuật XL

1 Giới thiệu
Giải thuật XL (Approximate Link-state) [5] được trình bày ở hội nghị SIGCOMM’08 (8/2008) bởi Kirill Levchenko thuộc khoa khoa học máy tính đại học California, San Diago. Đây là giải thuật định tuyến dành cho mạng link-state nhằm tăng hiệu quả định tuyến bằng cách giới hạn số lượng cập nhật thông qua việc gửi tràn có lựa chọn. Thông qua mô phỏng tác giả đã chứng minh rằng XL tốt hơn những giải thuật link-state hiện tại về thời gian đáp ứng cũng như tổng chi phí định tuyến tuy nhiên vẫn chưa có hiện thực nào để chứng minh mô phỏng trên.

2 Tổng quan
Giải thuật XL là giải thuật định tuyến cho mạng link-state. Giải thuật khác với các giải thuật khác là chỉ truyền một số cập nhật về trạng thái kết nối. Phần chính của giải thuật là ba luật cơ bản để truyền cập nhật trong mạng là:
• Khi chi phí cho việc cập nhật tăng lên (S1)
• Khi kết nối được dùng cho cây đường đi ngắn nhất của nút (S2)
• Khi chi phí đến đích bất kỳ vượt quá 1+e, e là thông số xấp xỉ thiết kế (C1)

Để thực hiện được những yêu cầu trên, mỗi nút phải lưu thêm hiểu biết của những nút xung quanh về trạng thái của mạng ở những thời điểm nhất định. So với những giải thuật link-state cơ bản thì XL yêu cầu thêm bộ nhớ để lưu trữ những hiểu biết của những nút kề về trạng thái của mạng nhưng sẽ giảm bớt lượng thông điệp gửi tràn khi thực hiện cập nhật tìm đường đi.

Tác giả cũng chứng minh hình thức rằng ba luật này là đủ và đúng để thực hiện định tuyến cho mạng link-state. Phần chứng minh hình thức có thể xem thêm trong tài liệu [5]. Mặc dù chưa hiện thực để kiểm chứng nhưng kết quả mô phỏng rất khả quan như hình 10 cho thấy thời gian đáp ứng và lượng thông tin điều khiển đều giảm đi đáng kể.


3 Ứng dụng
Giải thuật định tuyến XL mục đích là tối thiểu lượng thông tin điều khiển dùng để định tuyến, có thể kết hợp cùng với các giải thuật định tuyến link-state cũ. Giải thuật cũng có thể dùng với các thiết bị định tuyến cũ mà vẫn có thể tăng hiệu quả định tuyến của các thiết bị này mà không cần dùng các thiết bị định tuyến mới.