Định tuyến đảm bảo chất lượng dịch vụ trong MPLS

1 Định tuyến đảm bảo chất lượng dịch vụ trong MPLS ThS. Hoàng Trọng Minh Chuyển mạch nhãn đa giao thức (MPLS) là công nghệ đề xuất cho mạng lõi, nên yêu cầu đối với các cơ chế định tuyến trong MPLS cần phải đảm bảo tốc độ tính toán nhanh nhất và đạt hiệu năng tổng thể với cho nhiều luồng lưu lượng khác nhau. Hơn nữa, cải thiện hiệu năng định tuyến luôn là một bài toán được quan tâm hàng đầu trong mạng. Bài báo này giới thiệu và phân tích một số thuật toán cũng như giới thiệu một số hướng tiếp cận nhằm cải thiện hiệu năng định tuyến QoS trong mạng MPLS. 1. Giới thiệu chung Chất lượng dịch vụ (QoS) chính là một trong những yếu tố quan trọng nhất để thúc đẩy MPLS và nó luôn là một vấn đề lớn đối với kỹ thuật định tuyến không chỉ trong mạng MPLS. MPLS giải quyết bài toán QoS tương tự như mô hình phân biệt dịch vụ (Differs) trong IP, bằng cách hỗ trợ chất lượng dịch vụ trên cơ sở phân loại các luồng lưu lượng tại biên mạng. Các tham số ràng buộc về QoS của kết nối thường được đánh giá qua mức độ đảm bảo băng thông tối thiểu, độ trễ/trượt và tỉ lệ mất thông tin. Mục tiêu cơ bản của kỹ thuật định tuyến QoS là tìm ra một đường có khả năng đảm bảo các điều kiện ràng buộc của đấu nối và thậm chỉ để loại bỏ một số đấu nối khác. Một mô hình trạng thái mạng QoS thường được biểu diễn dưới dạng một đồ thị G(V,E). Trong đó V thể hiện cho các nút và E là các liên kết. Lưu lượng vào mạng qua nút Si và ra qua nút Ti. Mỗi liên kết (i,j) có 2 đặc tính : Ci,j là dung lượng liên kết và fi,j là lưu lượng thực tế. Gọi Ri,j = (Ci,j – fi,j) là băng thông dư. Một kết nối có yêu cầu băng thông là dk thì một liên kết được gọi là khả dụng khi Ri,j ≥ dk. Một kết nối mới có thể được chấp thuận nếu ít nhất tồn tại một đường dẫn khả dụng giữa Si và Ti . Một trong các khía cạnh then chốt của kỹ thuật định tuyến trong MPLS là hỗ trợ các đường dẫn hiện (nổi) dựa trên kỹ thuật chuyển tiếp nhãn, vì vậy thuật toán định tuyến trong MPLS cho phép lựa chọn các đường dẫn và các tham số chất lượng dịch vụ QoS để có được các kết quả tốt nhất. Yêu cầu chất lượng dịch vụ (QoS) của kết nối có thể được đưa ra như một tập các điều kiện ràng buộc, các điều kiện này có thể thể hiện rõ ràng như các yêu cầu về băng thông tối thiểu từ phía khách hàng, hoặc không tường minh như các yêu cầu về độ đàn hồi của mạng. Trong công nghệ chuyển mạch nhãn đa giao thức (MPLS), việc lựa chọn đường dẫn chuyển mạch nhãn (LSP) dựa trên phương pháp tìm đường ngắn nhất với điều kiện ràng buộc (CSPF) là giải pháp định tuyến động cơ bản trong mạng MPLS. Định tuyến ràng buộc đảm bảo chất lượng dịch vụ (CSPF) trong MPLS sử dụng một tập thuộc tính của trung kế lưu lượng [1], tập thuộc tính này liên quan tới tài nguyên và các thông 2 tin trạng thái khác của mạng. Dựa trên các thông tin này, một tiến trình định tuyến ràng buộc trên mỗi nút tự động tính toán tuyến hiện cho mỗi trung kế lưu lượng từ nút đó đi. Trong trường hợp chung, giải pháp để tìm đường dẫn khả dụng nếu nó tồn tại thường được tiến hành theo hai bước: Đầu tiên là loại bỏ toàn bộ các tài nguyên mà không thoả mãn các yêu cầu của trung kế lưu lượng (kết nối), sau đó chạy thuật toán tìm đường ngắn nhất trên đồ thị còn lại hoặc ngược lại. 2. Các thuật toán định tuyến QoS trong MPLS Trong phần này, giới thiệu một số thuật toán định tuyến QoS trong mạng MPLS đã được đề xuất như: Thuật toán Bước nhảy tối thiểu (Minhop -MHA) [2], thuật toán tìm đường ngắn nhất và rộng nhất (Widest Shortest Path -WSPA) [3], thuật toán tìm đường rộng nhất và ngắn nhất (Shortest Widest Path - SWPA) [4], thuật toán định tuyến nhiễu tối thiểu MIRA[5]. Hầu hết các phương pháp định tuyến trên đều chạy trên cơ sở thuật toán Dijkstra và tóm lược các ưu, nhược điểm của thuật toán sẽ được trình bày dưới đây theo từng thuật toán. Thuật toán bước nhảy tối thiểu (MHA) Thuật toán bước nhảy tối thiểu là thuật toán đơn giản nhất nhằm tìm ra một đường dẫn với số bước nhảy tối thiểu từ nguồn tới đích, mặc dù thuật toán này có khả năng tìm được đường dẫn đáp ứng được yêu cầu băng thông và có ưu điểm là tính toán nhanh, nhưng MHA gây ra hiện tượng nghẽn cổ chai tại liên kết tải lớn trong mạng. MHA có khuynh hướng sử dụng cùng một đường dẫn cho tới khi đạt tới tình trạng bão hoà trước khi chuyển sang các đường dẫn khác có mức tải thấp hơn. Thuật toán tìm đường rộng nhất và ngắn nhất (SWPA) Thuật toán tìm đường rộng nhất và ngắn nhất (SWPA) sử dụng băng thông như là một tham số đo lượng và lựa chọn đường dẫn với băng thông nghẽn cổ chai tối đa. Băng thông nghẽn cổ chai tối đa của một đường dẫn là băng thông dư tối thiểu trong tất cả các liên kết của một đường dẫn. Nếu có nhiều hơn một đường dẫn có cùng băng thông dư tối thiểu, thuật toán sẽ chọn đường có số lượng bước nhảy ít nhất. Nhược điểm của thuật toán này là ưu tiên băng thông nhằm tối ưu tải liên kết mà bỏ qua các tham số khác. Thuật toán định tuyến nhiễu tối thiểu (MIRA) Mục tiêu của thuật toán này là cung cấp đường dẫn có nhiễu ít nhất với các yêu cầu kết nối đường dẫn chuyển mạch nhãn (LSP) trong tương lai giữa các cặp nguồn – đích khác (Sj,Tj). thuật toán này giả thiết có một số nhận định về tiềm năng của các cặp nguồn- đích. Nhận định về tiềm năng của cặp nguồn- đích cho phép định tuyến lưu lượng mới dọc theo các đường dẫn không bị tới hạn bởi yêu cầu trong tương lai, vì vậy nó giảm được các số từ chối yêu cầu kết nối. Nhiễu của một đường dẫn có thể được định nghĩa như là sự suy giảm giá trị luồng tối đa của một cặp nguồn đích do vấn đề định tuyến trên cùng một LSP của các cặp nguồn đích khác. Các liên kết tới hạn là các liên kết khi sử dụng trong một hướng mới giữa một cặp nguồn-đích, nó làm suy giảm tốc độ luồng tối đa giữa các cặp khác. Nó tính toán 3 đường dẫn ngắn nhất bằng cách đặt giá liên kết là tham số tới hạn và chạy thuật toán Dijkstra. Nhược điểm của thuật toán này là sử dụng phương pháp tính nhằm đạt được tối đa số các yêu cầu, vì vậy nó có thể chọn các đường dẫn dài và tải cao thay vì các đường dẫn có số bước nhảy ngắn nhưng rơi vào tới hạn, điều đó sẽ dẫn tới tải tổng thể của mạng sẽ tăng lên. Hơn nữa, khi sử dụng các cặp nguồn –đích để tính các liên kết tới hạn, thuật toán không xác nhận tải thực tế sử dụng trên các cặp liên kết này, vì vậy mức ảnh hưởng của các cặp liên kết có tải khác nhau là khác nhau. Nhược điểm cuối cùng là MIRA không tính toán cho các yêu cầu trên cùng một cặp nguồn - đích (trường hợp tự can nhiễu). 3. Một số giải pháp cải thiện hiệu năng định tuyến QoS trong MPLS. Phần lớn các đề xuất trong thời gian gần đây tập trung vào giải quyết các nhược điểm của các thuật toán hoặc hướng tới giải quyết cân bằng các yêu tố như chiều dài đường dẫn, độ khả dụng tối đa và nhiễu, để đạt được các mục tiêu tương thích động của thuật toán định tuyến [6]. Một trong các đề xuất gần đây theo hướng đảm bảo băng thông kết nối trong MPLS, Antonio capone [2003] đề xuất giải pháp làm chệch luồng lưu lượng kết nối thông qua kỹ thuật làm chệch luồng ảo [7]. Để mô tả tốt nhất trạng thái hiện thời của mạng và dự đoán trạng thái tương lai, giải pháp đưa thêm thông tin về vị trí của các cặp nguồn-đích sử dụng bởi thuật toán MIRA, thống kê lưu lượng được đo trực tiếp trên các cặp kết nối và sử dụng như là một dữ liệu cơ sở để dự đoán các yêu cầu tiếp theo. Giải pháp lệch luồng ảo không chỉ sử dụng trên số liệu thống kê của các kết nối thực mà còn sử dụng các kết nối ảo để tính toán phân bố trạng thái giữa các cặp nguồn – đích nhằm tối ưu luồng tin về phương diện băng thông kết nối. Các kết quả mô phỏng trong [7] cho thấy khả năng giảm xác suất tắc nghẽn của thuật toán so với các thuật toán trước đây. Giải pháp cân bằng mục tiêu thường được giải quyết bằng cách đặt trọng số thích hợp cho các liên kết [5].Với mục tiêu cân bằng các yếu tố nhiễu và tải, tối thiểu mức tối đa của độ chiếm dụng liên kết. Yếu tố tải gồm hai thành phần: Tải trên liên kết thực tế và sự phân bổ liên kết làm tăng độ chiếm dụng tối đa. Như vậy, giá của liên kết có thể được tính trên mô hình đồ thị G(V,E) trên phần 1 với một số tham số bổ sung như sau: Trên mỗi liên kết fij là tải hiện thời, Cịj là dung lượng liên kết và α là mức chiếm dụng liên kết hiện thời lớn nhất. Đặt gij là tới hạn của liên kết và β là tới hạn lớn nhất của mạng. Bước khởi tạo đặt tập các tham số Fij , α, gij,β về giá trị zero và cập nhật chúng theo khoảng thời gian yêu cầu tạo tuyến. dk là yêu cầu cuối cùng. Giá liên kết được định nghĩa như sau: θij = (fij + dk )/ Cij + T1* max [ 0, ((fij + dk )/ Cij) - α] + T2 * (gij / β) (a) (b) (c) T1, T2 là các tham số điều hoà sử dụng để cân bằng giữa các mục tiêu được thể hiện qua 3 thành phần (a), (b), (c) trong công thức trên. 4 Thuật toán Dijstra lựa chọn tuyến theo giá thấp thất của các liên kết đi qua, trong giá liên kết đã nêu trên gồm 3 thành phần: phần (a) là độ chiếm dụng liên kết sau khi có yêu cầu lưu lượng mới, (b) thể hiện mức lớn nhất của chiếm dụng liên kết do việc chọn chính liên kết này, (c) chính là tới hạn chuẩn của liên kết. Như vậy, việc lựa chọn tuyến sẽ dựa trên một loạt các yêu cầu ràng buộc và trọng số của liên kết sẽ quyết định tuyến tương ứng với tiêu chí tối ưu mà mạng yêu cầu theo phương pháp trực tuyến, lựa chọn tham số điều hòa T1, T2 để thay đổi trọng số, nhằm tiệm cận với bài toán tương thích động của phương pháp định tuyến động. 4. KẾT LUẬN Kỹ thuật định tuyến đảm bảo chất lượng dịch vụ QoS trong mạng đa dịch vụ luôn là một vấn đề cần quan tâm của các nhà khai thác và cung cấp dịch vụ mạng. Đã có rất nhiều nghiên cứu được tiến hành và sẽ còn tiếp tục trong tương lai. Thông qua bài báo, tác giả mong muốn cung cấp thông tin cho người đọc một cách nhìn về kỹ thuật định tuyến QoS trong mạng MPLS, qua các tìm hiểu về các thuật toán hiện đang sử dụng trong mạng MPLS và hai hướng tiếp cận gần đây nhằm nâng cao hiệu năng thuật toán định tuyến. Tài liệu tham khảo [1]. BRUCEDAVIE and YAKOV REKHTER, MPLS Technology and Applications, Morgan Kaufmann Pulishers, Inc. 2000. [2]. D.O.AWDUCHE, L.BERGER, D.GAIN, T.LI, G.SWALLOW, and V.SRINIVASAN. Extensions to RSVP for LSP Tunnels. In Internet Draft draft-ietf-mpls-rsvp-lsp-tunnel-04.txt, September 1999. [3]. R.GUERIN, D.WILLIAMS, and A.ORDA, QoS Routing Mechanisms and OSPF Extensions, In Proceedings of Globecom, 1997. [4 ]. Z. WANG and J. CROWCROFT, Quality-of-Service Routing for Supporting Multimedia Applications,.IEEE JSAC,14(7):1288-1234, September 1996. [5]. MURLI KODIALAM, T.V.LAKSHAM, Minimum Interference Routing with Applications to MPLS Traffic Engineering, June 2000. [6]. HOÀNG TRỌNG MINH, Định tuyến trong chuyển mạchIP, Tạp chí BCVT, 3-2003. [7]. ANTONIO CAPONE, LUI FRATTA, FABIO MARTIGNON, Dynamic routing of bandwidth guaranteed connections in MPLS networks, International Jounal on Wireless & Optical Communication Vol.1, No.1 (2003).