Định tuyến qos sử dụng thông tin nội bộ đảm bảo trễ end-to-end

Nội dung text: Định tuyến qos sử dụng thông tin nội bộ đảm bảo trễ end-to-end

1. Nguyễn Chiến Trinh, Nguyễn Thị Thu Hằng ĐỊNH TUYẾN QOS SỬ DỤNG THÔNG TIN NỘI BỘ ĐẢM BẢO TRỄ END-TO-END Nguyễn Chiến Trinh*, Nguyễn Thị Thu Hằng* * Học viện Công nghệ Bưu chính Viễn thông 1Tóm tắt: Định tuyến QoS đảm bảo các chỉ tiêu trễ được phân loại định tuyến nguồn, định tuyến phân tán và đầu cuối cho các ứng dụng Internet là một trong những định tuyến phân cấp. giải pháp đảm bảo chất lượng dịch vụ quan trọng, đặc Các ứng dụng thời gian thực thường có các yêu cầu chất biệt là cho các ứng dụng thời gian thực như đa phương lượng dịch vụ nghiêm ngặt, được thỏa thuận giữa nhà cung tiện. Trong thời gian gần đây định tuyến QoS sử dụng cấp và người sử dụng. Các ứng dụng nhạy cảm trễ, như đa thông tin nội bộ đã được đề xuất với nhiều ưu thế so với phương tiện, yêu cầu dòng lưu lượng phải đến đích trong định tuyến truyền thống sử dụng thông tin toàn cục trên giới hạn thời gian nhất định (trễ end-to-end). Đảm bảo QoS mạng IP. Giải pháp này giảm được quá trình duy trì, giám là một vấn đề rất nan giải do trên mạng có nhiều loại ứng sát thông tin tại các nút mạng, nâng cao hiệu năng định dụng với các đặc tính lưu lượng khác nhau hoặc tích hợp tuyến. Định tuyến QoS với đảm bảo trễ đòi hỏi tìm đường nhiều loại dịch vụ. Trong các giải pháp định tuyến sử dụng truyền đầu cuối đáp ứng các ràng buộc về trễ end-to-end, thông tin toàn cục, thông tin trạng thái toàn mạng sử dụng thường là bài toán khó hơn đảm bảo băng thông chỉ liên để tính toán định tuyến phải được giám sát tại mỗi nút mạng quan đến yêu cầu của từng liên kết. Trong bài báo này đề và phải cập nhật liên tục. Tuy nhiên, do cấu trúc mạng và xuất giải thuật định tuyến QoS sử dụng thông tin nội bộ khả năng sẵn sàng của tài nguyên luôn thay đổi, duy trì đảm bảo trễ (Localized Delay-Constrained QoS Routing giám sát trạng thái mạng chính xác là không thể thực hiện, - LDCQR) kết hợp dự báo trễ (Delay Prediction – DP) ngoài ra giải pháp này còn tạo thêm lưu lượng đáng kể cũng đảm bảo chỉ tiêu trễ đầu cuối trong suốt thời gian tồn tại như làm phức tạp quá trình xử lí trên mạng. Mặt khác, quyết định định tuyến được tiến hành mà không xem xét luồng lưu lượng với độ chính xác và cải thiện hiệu năng. đến trạng thái mới nhất của tài nguyên mạng có thể dẫn đến Giải thuật LDCQR-DP được kiểm chứng thông qua mô việc định tuyến trên đường không thỏa mãn các yêu cầu phỏng số, khẳng định hiệu quả định tuyến QoS và tỉ lệ QoS [1]. Do vậy, có thể dẫn đến giảm hiệu năng mạng và đảm bảo trễ yêu cầu. các tuyến khác có đủ tài nguyên nhưng lại không được sử Từ khóa: Định tuyến QoS, trễ đầu cuối, định tuyến dụng. sử dụng thông tin nội bộ, dự báo trễ. Khác với các giải pháp định tuyến QoS sử dụng thông I. GIỚI THIỆU tin toàn cục, gần đây các giải pháp định tuyến QoS sử dụng Trên Internet các dịch vụ khác nhau được triển khai với thông tin nội bộ [2-4] đã được đề xuất để khắc phục vấn đề các yêu cầu khác nhau. Các dịch vụ này yêu cầu các ràng phải duy trì và giám sát thông tin trạng thái tại mỗi nút buộc xác định bằng các chỉ tiêu QoS như băng thông, độ mạng. Tại các nút mạng, các giải thuật định tuyến sử dụng trễ. Giải thuật định tuyến đóng vai trò then chốt để đáp ứng thông tin nội bộ lấy thông tin thống kê (thu thập qua quá các ràng buộc này bằng cách thỏa mãn chỉ tiêu QoS trên trình định tuyến và truyền luồng) tại nút mạng đó, và từ đó đường định tuyến được chọn khi truyền luồng lưu lượng từ tính toán, đưa ra quyết định định tuyến. Giải thuật định nguồn đến đích. Đảm bảo QoS cho luồng nghĩa là đảm bảo tuyến sử dụng thông tin nội bộ giúp giảm khối lượng tính chỉ tiêu QoS không vượt quá ngưỡng cho trước [1]. Do vậy toán tuyến truyền tại các nút mạng, giảm thiểu bộ nhớ dành định tuyến QoS về bản chất là tìm đường có đủ tài nguyên cho các bảng định tuyến, cũng như giảm khối lượng bản tin đáp ứng các ràng buộc QoS. Với mục tiêu nâng cao hiệu cập nhật trạng thái định kỳ như trong các giải thuật định năng mạng truyền thông và đảm bảo chất lượng dịch vụ, tuyến toàn cục truyền thống, đồng thời hỗ trợ việc tính toán đặc biệt là các ứng dụng thời gian thực như đa phương tiện tập trung, điều khiển phân tán trên toàn mạng. liên quan đến thoại, video, âm thanh, hình ảnh, định tuyến Ràng buộc QoS thường là ràng buộc kết nối hoặc ràng QoS đảm bảo các chỉ tiêu trễ đầu cuối là một trong những buộc đường định tuyến. Ràng buộc kết nối giới hạn sử dụng vấn đề phải giải quyết. Quá trình định tuyến thường bao tài nguyên kết nối khi lựa chọn đường định tuyến, ví dụ gồm hai giai đoạn: thu thập thông tin trạng thái mạng tại như băng thông phải lớn hơn hoặc bằng giá trị xác định cho thời điểm xác định và tìm các thông tin trạng thái cho kết nối trên đường định tuyến khả dụng. Định tuyến với đường khả dụng đáp ứng yêu cầu QoS. Việc tìm đường khả ràng buộc kết nối thường thực hiện trực tiếp và dễ dàng dụng đáp ứng yêu cầu QoS chủ yếu phụ thuộc vào việc hơn do đường định tuyến có kết nối không thỏa mãn điều thông tin trạng thái được thu thập như thế nào và lưu giữ ở kiện ràng buộc sẽ bị loại bỏ. Mặt khác, ràng buộc đường đâu. Dựa trên thông tin được duy trì, xử lí và đường định định tuyến là tổng hợp các số đo trên toàn bộ đường không tuyến được chọn như thế nào, quá trình định tuyến thường được vượt quá một giới hạn, như trễ end-to-end của luồng lưu lượng trên đường định tuyến không được vượt quá giá Tác giả liên hệ: Nguyễn Chiến Trinh, Email: chientrinh@gmail.com Đến tòa soạn: 9/2020, chỉnh sửa: 10/2020, chấp nhận đăng: 12/2020
2. ĐỊNH TUYẾN QOS SỬ DỤNG THÔNG TIN NỘI BỘ ĐẢM BẢO TRỄ END-TO-END trị xác định. Trễ là tham số có tính cộng, trễ end-to-end bao nút nguồn. Khi một luồng dữ liệu đến, một tuyến truyền gồm trễ trên tất cả các kết nối của đường truyền cộng với được lựa chọn từ tập ứng cử theo tiêu chí nhất định của giải trễ tại các nút mạng. Vì trễ là ràng buộc đường định tuyến, thuật, ví dụ giá trị trung bình của trễ đầu cuối thấp nhất sẽ tìm đường khả dụng sẽ khó khăn hơn so với định tuyến được chọn [10], hay tuyến có tỉ lệ nghẽn luồng thấp nhất ràng buộc băng thông và là bài toán NP khó. được chọn [9]. Giá trị thống kê đánh giá tuyến được xem như là thước đo của chất lượng tuyến truyền và là tiêu chí Trong bài báo này đề xuất giải thuật định tuyến nguồn chọn đường từ tập các tuyến ứng cử. sử dụng thông tin nội bộ đảm bảo trễ đầu cuối trung bình trên chu kì thời gian tùy ý cho luồng dữ liệu, đạt được độ Để kiểm tra ràng buộc trễ QoS của tuyến được chọn, chính xác cũng như cải thiện hiệu năng định tuyến. Bài báo định tuyến QoS sử dụng bản tin kiểm tra đo trễ QoS trên được bố cục như sau, Phần II giới thiệu các kĩ thuật cơ bản tuyến. Bản tin được truyền qua tất cả các nút của tuyến và của định tuyến sử dụng thông tin nội bộ cũng như khảo sát cập nhật thông tin QoS tuyến được chọn, sau đó phản hồi các công trình nghiên cứu liên quan tiếp cận định tuyến về nút nguồn. Do vậy, có thể thấy tuyến được chọn chỉ QoS với ràng buộc trễ end-to-end. Phương pháp tính trễ được đánh giá dựa trên giá trị trễ tức thời được đo bằng bản đầu cuối áp dụng trong giải thuật định tuyến được đưa ra tin kiểm tra, không phản ánh được giá trị trễ trung bình trong Phần III. Giải thuật định tuyến QoS đề xuất LDCQR- mong muốn của tuyến trên toàn bộ khoảng thời gian tồn tại DP đảm bảo trễ end-to-end được trình bày trong Phần IV. của luồng. Đồng thời do sự thay đổi liên tục của trạng thái Các đánh giá thông qua mô phỏng số khẳng định tính hiệu mạng, trễ tức thời đo được không thể phản ánh chính xác quả và đóng góp của giải thuật đề xuất được đưa ra trong trễ end-to-end trong khoảng thời gian tiếp theo khi chấp Phần V. Cuối cùng là Kết luận và các thảo luận. nhận truyền luồng yêu cầu. Việc sử dụng bản tin kiểm tra trong quá trình định tuyến cũng làm tăng thêm lưu lượng II. CÁC CÔNG TRÌNH LIÊN QUAN dư thừa trên mạng. Giải thuật đề xuất trong bài báo này sử Đối với các giải thuật định tuyến sử dụng thông tin nội dụng phương pháp dự báo trễ end-to-end trung bình trong bộ, nút nguồn cố gắng suy luận trạng thái mạng từ các chu kì độ dài bất kì sẽ giải quyết vấn đề còn tồn tại này, thống kê luồng nội bộ và chọn tuyến truyền từ nguồn đến đảm bảo độ chính xác khi tiến hành kiểm tra ràng buộc QoS đích [2-4]. Mỗi nút mạng duy trì một tập xác định trước và không làm tăng thêm lưu lượng mạng, nâng cao được các tuyến ứng cử đến tất cả các nút. Hai phương pháp chọn hiệu năng của định tuyến QoS. đường cơ bản trong định tuyến sử dụng thông tin là Proportional Sticky Routing (PSR) [4] và Credit Based III. DỰ BÁO TRỄ END-TO-END Routing (CBR) [5]. Việc chọn đường từ tập các ứng cử Với mục tiêu đảm bảo các tham số trễ đầu cuối cho luồng đóng vai trò then chốt ảnh hưởng đến hiệu năng định tuyến, lưu lượng, cơ sở của giải thuật định tuyến QoS đảm bảo trễ và phải tối ưu giữa độ dài tuyến, cân bằng tải, và chỉ tiêu LDCQR-LP, trong phần này thiết lập bài toán kiểm soát và QoS yêu cầu. dự báo trễ end-to-end cho các tuyến truyền trên mạng. Phương pháp dự báo trễ end-to-end cho tuyến đưa ra trong Để đảm bảo mức QoS trên mạng, giải thuật định tuyến phần này là ý tưởng hoàn toàn mới và lần đầu tiên được áp QoS phải truyền lưu lượng yêu cầu từ nguồn đến đích trên dụng vào các giải thuật định tuyến QoS. tuyến thỏa mãn các ràng buộc QoS. Quá trình định tuyến thường bao gồm chọn tuyến thích hợp cho mỗi luồng, thiết A. Mô hình định tuyến đảm bảo trễ đầu cuối lập điều khiển chấp nhận (admission control) để kiểm tra Xét trên một đường định tuyến có L liên kết giữa hai tính sẵn sàng của tài nguyên mạng và cuối cùng là dự trữ nút mạng đầu SS và nút mạng cuối SD và các nút mạng tài nguyên như băng thông cần thiết trong suốt chu kì tồn (hop) trung gian Sl, với (l=1, ,L-1). Như vậy trễ đầu cuối tại của luồng. Nhiệm vụ chủ yếu của giải thuật định tuyến 푖 của gói tin i xét tại thời điểm bất kì của tuyến được tính sử dụng thông tin nội bộ là phân bổ các luồng đến nút trên bằng các tuyến của tập ứng cử. Nút nguồn có thể đánh giá chất 퐿−1 푙 lượng truyền luồng thông qua phản hồi từ các luồng được 푖 = ∑ =1 푖 + (1) truyền trước đó và thông tin thống kê tại nút. Do trạng thái 푙 mạng thay đổi liên tục, dự đoán chất lượng các tuyến cũng Trong đó 푖 là trễ tại nút Sl, là trễ truyền lan của phải thay đổi thích nghi, phản ánh kịp thời chất lượng của gói tin trên tuyến. Trễ truyền lan được xem như một 푙 tuyến truyền. hằng số đối với tuyến truyền xác định, còn trễ 푖 bao gồm ba thành phần chính: trễ hàng đợi phụ thuộc vào trạng thái Các ứng dụng khác nhau yêu cầu các ràng buộc QoS của mạng, được tính trên độ dài hàng đợi bộ đệm, trễ xử lí khác nhau, như trễ đầu cuối, thông lượng hay băng thông và trễ truyền dẫn là đại lượng thường không đáng kể, và có cho các luồng lưu lượng đến. Các nghiên cứu định tuyến thể được tính như một hằng số tại nút mạng xác định. Trong QoS thường tập trung đảm bảo băng thông QoS hoặc các các phân tích và nghiên cứu về hệ thống viễn thông kinh điều kiện liên quan đến thông lượng [6-9]. Mỗi luồng lưu điển đã chỉ ra rằng trễ hàng đợi tại một nút mạng là một lượng đến yêu cầu một lượng băng thông sẵn sàng để luồng biến ngẫu nhiên ổn định có các tham số và phân bố phụ truyền trên mạng. Nếu lượng băng thông này sẵn sàng trên thuộc vào mô hình lưu lượng đến, độ dài bộ đệm và tốc độ đường định tuyến được chọn, thì luồng được chấp nhận và truyền thông liên kết đầu ra. Do vậy, có thể xem xét đại QoS được đảm bảo. 푙 lượng 푖 như một biến ngẫu nhiên với phân bố xác định, Đối với các ứng dụng thời gian thực, trễ đầu cuối là tiêu dẫn đến 푖 cũng sẽ là một biến ngẫu nhiên ổn định, có cùng chí QoS quan trọng nhất. Trễ end-to-end của đường định phân bố cho tất cả gói tin i thuộc cùng một tuyến. Trong tuyến xem xét ở đây là trễ trung bình đo trên khoảng thời phương pháp định tuyến QoS dựa trên phân tích tại từng 푙 gian nhất định. Các giải thuật định tuyến đảm bảo trễ end- nút mạng trung gian, các tham số trễ 푖 được tính toán dựa to-end [9, 10] giải quyết cả hai vấn đề: đảm bảo các ràng trên hệ thống hàng đợi với các mô hình lưu lượng đầu vào buộc trễ đầu cuối trên đường định tuyến và tối ưu định xác định. Đã có rất nhiều các kết quả nghiên cứu cho các tuyến. Tối ưu định tuyến là tìm đường thỏa mãn các điều mô hình lưu lượng khác nhau (mô hình Poisson, lưu lượng kiện QoS đồng thời tối thiểu tỉ lệ nghẽn luồng quan sát trên phụ thuộc trường kì, ) đưa ra phân bố trễ và tính toán các
3. Nguyễn Chiến Trinh, Nguyễn Thị Thu Hằng tham số trễ, mất gói, Một hạn chế của phương pháp này được đặc tính của giá trị cực đại mà không cần mô hình hóa là phải biết được mô hình và các tham số lưu lượng mạng, hay thống kê để biết được phân bố biến ngẫu nhiên trễ gói đòi hỏi số liệu thống kê lớn và khó đạt được trên mạng hỗn tin 푖, thường đòi hỏi lượng lớn dữ liệu và tính toán phức tạp hiện nay. Đồng thời, đây cũng là phương thức sử dụng tạp, và không khả thi trong điều kiện mạng có dung lượng thông tin toàn cục để tính toán trễ, không phù hợp với giải lớn. Do vậy, có thể biểu diễn hàm phân bố pháp định tuyến sử dụng thông tin nội bộ. Phương pháp thứ ( ) [ ] −푒−( −휇)/훽 hai dựa trên các phép đo và thử nghiệm, 푖 được đo trực 퐹 = 푃 MK, thiết lập M các nhóm liên tiếp Tại thời điểm t, từ M mẫu trễ cực đại đầu cuối đã được thu bao gồm K gói tin, bắt đầu từ gói tin n-MK, trên mỗi nhóm thập từ M nhóm gói tin trong quá khứ (m=1,2, lấy giá trị trễ lớn nhất của nhóm M), chúng ta sẽ ước lượng các tham số của biến trễ cực đại +1 cho nhóm K gói tin tiếp theo. Trước hết tính = max 푖 với m=1,2, (2) giá trị trung bình thống kê của 푛−( − )퐾≥푖≥푛−( − +1)퐾 ∑푗=1 푗 Trễ cực đại trong nhóm K gói tin liên tiếp là ̅ = (8) giá trị trễ lớn nhất từ K mẫu của cùng phân bố trễ đầu cuối 푖, tạo thành hàm đường bao của trễ đầu cuối. Giả sử các Thiết lập hàm số tương quan của biến ngẫu nhiên 푖 không phụ thuộc, xuất phát từ lí thuyết 푪풐풓(풊) = 푬[푫 풙풋푫 풙풋+풊] với j=1,2, ,M-i. (9) giá trị vượt trội hàm phân bố của (m=1,2, ) có thể được biểu diễn qua hàm phân bố F của 푖 như sau [6]: Với E[] là hàm lấy giá trị trung bình của biến ngẫu 퐾 nhiên. Hàm tương quan có thể được ước lượng từ các mẫu 퐹 ( ) = 퐹 ( ) (3) của như sau Và nếu có được phân bố của có thể suy ngược 푴−풊 ∑ 푫 풙풋푫 풙풋+풊 lại hàm phân bố 푖, 푪풐풓(풊) = 풋= (10) 푴−풊 1/퐾 퐹( ) = [퐹 ( )] (4) Giá trị trung bình của 푫 풙푴+ có thể được tính bằng Các số đo thống kê và phân tích cũng chỉ ra rằng trễ đầu − 푫̂ 풙푴+ = 푫̅ 풙 + 횪 횪 횿 (11) cuối 푖 có các đặc tính phụ thuộc chủ yếu vào thành phần trễ hàng đợi, là biến ngẫu nhiên có phân bố được ước lượng Trong đó tương đối chính xác bằng các hàm heavy-tailed như Gamma, Weibull, Pareto, [11,12]. Điều này hoàn toàn 횪 = [휸 ,푴, 휸 ,푴, , 휸푴,푴] ; phù hợp với lí thuyết và phân tích hệ thống hàng đợi tại các 횪 là ma trận MxM có các phần tử 후 ; bộ định tuyến với bản chất của lưu lượng mạng Internet 풊,풋 dạng phụ thuộc trường kì (long-range dependent) [13-15]. 횿 = [푫 풙푴 − 푫̅ 풙, 푫 풙푴− − Trong [16], đối với phần lớn các dạng phân bố thường gặp 푻 푫̅ 풙, , 푫 풙 − 푫̅ 풙] như Gamma, log-normal, Gausian, đều cho kết quả ước ̅ lượng phân bố của biến cực đại là Gumbel (hay còn gọi là 후풊,풋 = 푪풐풓(풊 − 풋) − (푫 풙) phân bố giá trị vượt trội tổng quát – loại I) với lựa chọn giá Phương sai lỗi của ước lượng giá trị trung bình trị cực đại trong số lượng K mẫu là lớn. Phương pháp ước 푫̂ 풙 cũng chính là phương sai của biến ngẫu nhiên lượng giá trị cực đại của biến ngẫu nhiên bất kì bằng phân 푴+ bố Gumbel đã từng được sử dụng và cho kết quả khá chính 푫 풙푴+ xác trong các ứng dụng khác nhau, như để ước lượng giá ̂ − 흈 풙푴+ = 흈 풙 + 횪 횪 횪 (12) trị cực đại lưu lượng mạng [17,18]. Ưu điểm lớn nhất khi ước lượng bằng phân bố Gumbel là cho phép tìm Trong đó
4. ĐỊNH TUYẾN QOS SỬ DỤNG THÔNG TIN NỘI BỘ ĐẢM BẢO TRỄ END-TO-END 푴 được sử dụng như tiêu chí cho quá trình lựa chọn tuyến. 흈 풙 = ∑풊= [푫 풙풊 − 푫̅ 풙] 푴 Mỗi khi có luồng mới đến, tuyến đường với trễ end-to-end 푻 횪 = [휸 , 휸 , , 휸 ] trun g bình dự báo nhỏ nhất sẽ được chọn để truyền luồng 푴, 푴, 푴,푴 yêu cầu. Như vậy, trễ end-to-end trung bình dự báo được D. Dự báo các tham số trễ end-to-end sử dụng như tiêu chí đánh giá chất lượng của tuyến ứng cử Trên cơ sở ước lượng đường bao trễ và xác định phân trong thời gian sử dụng truyền luồng, đáp ứng tham số QoS bố trễ đầu cuối cho một tuyến bất kì dựa trên số liệu trễ luồng yêu cầu được truyền. Do vậy đảm bảo được tính thống kê tại tuyến, các tham số trễ của tuyến được dự báo chính xác khi đảm bảo trễ QoS cho luồng khi truyền trong như sau. Giả sử tại thời điểm t xuất hiện yêu cầu định tuyến thời gian tiếp theo, khác với các phương pháp trước đây cho một luồng lưu lượng có độ dài bất kì. Chia luồng lưu [9.10], chỉ có thể sử dụng các tham số trễ quá khứ được đo lượng thành các đoạn có độ dài K gói tin và dự báo trễ đầu bằng các gói thử nghiệm, để đánh giá, lựa chọn, và kiểm cuối trung bình cũng như jitter cho từng đoạn dữ liệu này: tra đường định tuyến. Ngoài ra, sử dụng tiêu chí chọn đường với trễ dự báo nhỏ nhất có thể đảm bảo tuyến được • Thống kê KM mẫu trễ đầu cuối trước thời điểm t chọn là khả thi nhất để đảm bảo trễ luồng yêu cầu, do đó cho tuyến đường ứng viên từ nút mạng nguồn SS cũng đảm bảo khả năng nghẽn luồng có thể xảy ra là thấp đên nút mạng cuối SD; nhất. Đồng thời mỗi lần định tuyến, các thông tin về trễ của luồng cũng sẽ được thống kê để sử dụng như các thông tin • Từ MK mẫu trễ đầu cuối lấy M mẫu trễ cực đại trạng thái đánh giá chất lượng tuyến và cập nhật số liệu cho trong mỗi nhóm K gói tin liên tiếp ; các dự báo tiếp theo. • Đối với tuyến xem xét p, dự báo giá trị trung bình Với phương pháp dự báo và chọn tuyến như vậy, và phương sai trễ cực đại +1 của K gói tin LDCQR-DP sẽ tránh được quá trình kiểm tra chất lượng tiếp theo; tuyến được chọn, thực hiện bằng các bản tin kiểm tra như trong các giải thuật định tuyến QoS sử dụng thông tin nội • Xác định phân bố +1 theo (5) với các tham số được tính từ (6) và (7); bộ truyền thống [9,10]. Do vậy giảm được độ trễ định tuyến, độ phức tạp của quá trình định tuyến, cũng như lưu • Ước lượng phân bố trễ đầu cuối 푖 của K gói tin lượng đánh giá trạng thái mạng. Yêu cầu truyền luồng lưu của đoạn dữ liệu yêu cầu (4); lượng sẽ bị chối bỏ nếu giá trị trễ trung bình dự báo trên tất cả các tuyến ứng cử đều không thỏa mãn giá trị trễ QoS • Ước lượng các tham số trễ cơ bản của đoạn dữ yêu cầu. Tỉ lệ yêu cầu luồng bị chối bỏ thường được gọi là liệu yêu cầu tỉ lệ nghẽn luồng. 1) Giá trị trễ trung bình: Ngoài phương pháp đánh giá chất lượng tuyến truyền ∞ và sử dụng làm tiêu chí lựa chọn đường bằng trễ end-to- [ 푖] = ∫ 퐹( ) (13) 0 end trung bình (13) trong LDCQR-DP, các kết quả dự báo 2) Độ lệch chuẩn của trễ đầu cuối: trong Phần III cũng cho phép có thể phát triển các giải thuật 1/2 1/2 định tuyến QoS khác với các tham số như jitter (14), tỉ lệ 2 2[ ] ∞ 2 2[ ] ( [ 푖 ] − 푖 ) = (∫0 퐹( ) − 푖 ) trễ vượt ngưỡng (15), hay kết hợp nhiều tham số QoS, đáp (14) ứng các đòi hỏi khác nhau của dịch vụ phức hợp. 3) Tỉ lệ trễ vượt ngưỡng 푄표푆 cho trước: Một trong những vấn đề cần xem xét là lựa chọn giá trị tham số K và M tham gia trong quá trình dự báo của 푃[ 푖 > 푄표푆] = 1 − 퐹( 푄표푆) (15) LDCQR-DP. Thực tế K càng nhỏ, dự đoán và ước lượng các tham số trễ được thực hiện trên các đoạn dữ liệu qui Độ phức tạp tính toán của giải thuật ước lượng trễ được mô nhỏ sẽ đảm bảo tính thích nghi với sự biến đổi của trễ quyết định bởi các giải thuật dự báo tuyến tính tham số trễ mạng. Đồng thời, thích hợp cho các luồng dữ liệu có thời cực đại, phụ thuộc vào số lượng mẫu dự báo M, do vậy có gian tồn tại không dài. Tuy nhiên, K nhỏ sẽ đòi hỏi tần suất bậc là ( 2). tính toán lớn hơn, và chu kì xác định đường định tuyến sẽ IV. GIẢI THUẬT ĐỊNH TUYẾN LDCQR-DP phải diễn ra liên tục, tăng độ phức tạp của giải thuật. Giá trị M đơn thuần tác động đến độ chính xác của giải thuật Mục tiêu của giải thuật LDCQR-DP là đảm bảo trễ QoS dự báo tuyến tính. Số mẫu M càng lớn càng đảm bảo độ end-to-end từ khía cạnh người sử dụng và đồng thời tối ưu chính xác, tuy nhiên sẽ kéo theo yêu cầu tăng dung lượng tỉ lệ nghẽn mạng từ khía cạnh mạng. LDCQR-DP là giải bộ nhớ lưu trữ các mẫu, và tăng độ phức tạp của thuật toán thuật định tuyến nguồn, nút nguồn sẽ tính toán lựa chọn dự báo. Giải pháp định tuyến QoS đòi hỏi thống kê số tuyến đường khả thi nhất có thể đáp ứng các điều kiện QoS lượng các mẫu lớn và liên tục, do vậy thông thường phù của luồng. Dựa trên các thông tin trạng thái thu thập được hợp cho quá trình định tuyến trên mạng giữa các bộ định tại nút mạng, LDCQR-DP tiến hành dự báo trễ end-to-end tuyến, hoặc giữa các thiết bị đầu cuối có lưu lượng truyền trung bình trên khoảng thời gian tồn tại của luồng yêu cầu thông cao. để quyết định lựa chọn tuyến truyền. Cũng như tất cả các giải thuật định tuyến sử dụng thông V. MÔ PHỎNG VÀ ĐÁNH GIÁ tin nội bộ, tại mỗi nút nguồn LDCQR-DP phải duy trì một A. Mô hình mô phỏng kiểm thử tập các đường ứng cử cho mỗi cặp nguồn-đích. Phương Để khảo sát hoạt động của giải pháp đề xuất mô phỏng pháp chọn các đường ứng cử có thể sử dụng giống như áp thử nghiệm được tiến hành trên mô hình tuyến p bao gồm dụng trong CBR và các giải thuật đã đề xuất [5-9]. Tập ứng 5 liên kết kết nối với nhau theo thứ tự từ 1 đến 5 (Link 1 cử giữa cặp nguồn-đích thường bao gồm các tuyến có độ đến Link 5) và đương định tuyến p từ nguồn (Source) tới dài minhop và (minhop+1). Trễ trung bình end-to-end trên đích (Destination). Mô hình mạng và đường định tuyến giả mỗi tuyến ứng cử (được dự báo từ công thức (13) Phần III)
5. Nguyễn Chiến Trinh, Nguyễn Thị Thu Hằng lập trên cơ sở mạng thực tiễn đơn giản bao gồm 3 phần Tổng 83,93 78,68 65,57 mạng truy nhập, mạng MAN và mạng lõi. tải Luồng lưu lượng nút nguồn gửi đến nút đích được thiết liên lập với tốc độ 100 Mbps. Tốc độ của liên kết 1 (Link 1) và kết liên kết 5 (Link 5) ấn định bằng 10 Gbps; tốc độ liên kết 2 B. Đánh giá tính chính xác của thuật toán dự báo trễ end- (Link 2) và 4 (Link 4) là 80 Gbps; và tốc độ liên kết 3 (Link to-end 3) là 480 Gbps. Tương ứng với mỗi liên kết, chúng ta ấn định bộ đệm sao cho trễ hàng đợi tối đa trên liên kết không Trước hết độ tin cậy, tính khả thi của giải pháp đề xuất vượt quá 100 ms, đủ lớn để đảm bảo tỉ lệ mất gói và tránh được đánh giá thông qua tính chính xác của các tham số trễ tắc nghẽn. Trên tuyến p lấy tổng thành phần trễ truyền dẫn đầu cuối ước lượng cho luồng u khi được định tuyến trên và truyền lan tại mỗi nút mạng trung gian là 4 ms, tương p. Tại thời điểm t tiến hành thử nghiệm và đánh giá quá đương tổng trễ truyền dẫn và truyền lan của cả tuyến là 24 trình định tuyến của luồng lưu lượng u với độ dài trên 5 ms. triệu gói tin được chia thành các nhóm K gói tin. Thử nghiệm được thực hiện trên nhiều giá trị M khác nhau - số Lưu lượng sử dụng trong mô phỏng được xây dựng dựa nhóm gói tin thống kê và quan sát trong quá khứ để ước trên các phân tích và đo lường lưu lượng mạng Internet lượng trễ khoảng thời gian tiếp theo. Tuy nhiên kết quả thử thực tế. Lưu lượng mạng hỗn tạp bao gồm 8 lớp lưu lượng nghiệm cho thấy không có sự sai lệch nhiều về độ chính phân biệt, tại mỗi nút các gói tin được xử lí theo cơ chế xác đối với các giá trị M đủ lớn. Điều này cũng hoàn toàn phân biệt dịch vụ (DiffServ). Lưu lượng trên mỗi lớp được hợp lí, do kết quả dự báo chủ yếu phụ thuộc vào các mẫu tạo thành bằng cách tổng hợp một số nguồn lưu lượng mô mới nhất, có mối tương quan lớn hơn với dữ liệu dự báo. hình ON-OFF. Trong chu kỳ ON, các gói tin được tạo ra Do vậy, để đảm bảo tính toán thời gian thực, có thể lấy để đạt tốc độ lưu lượng 1 Gbps; trong chu kì OFF, không M=100 mà vẫn đảm bảo độ chính xác dự báo. Kết quả ước có gói tin nào được tạo ra. Để đơn giản hóa tính toán mà lượng trễ trung bình với số lượng gói tin trong mỗi nhóm không làm mất đặc tính thống kê của lưu lượng, cũng như lưu lượng của luồng K=1000 được đưa ra trong được Hình không ảnh hưởng đến hoạt động của giải thuật định tuyến, 1. Có thể thấy giải thuật ước lượng cho các giá trị trễ trung có thể sử dụng các gói có độ dài cố định. Trong trường hợp bình khá chính xác, có thể đáp ứng sử dụng cho các phương thử nghiệm này, chọn độ dài gói tin 500 byte. Phân bố và pháp định tuyến QoS trên mạng. các tham số cho các lớp lưu lượng được đưa ra trong Bảng I. Đối với các lớp lưu lượng có phân bố Pareto tham số hình Ước lượng trễ trung bình dạng (shape parameter) được chọn bằng 1.3, tương ứng với tham số Hurst đặc trưng cho tính bùng nổ của dòng lưu 250 lượng bằng 0.85. Các tham số sử dụng trong mô hình lưu 200 lượng này như phân bố và độ dài các chu kì ON, OFF được 150 tham khảo từ các giá trị thống kê lưu lượng mạng Internet thực tiễn, đã được sử dụng trong các nghiên cứu mô hình 100 hóa lưu lượng [13-15]. Mô phỏng được tiến hành với tải 50 trọng khác nhau trên mỗi liên kết, nhằm thử nghiệm hoạt 0 động của giải pháp đề xuất với các điều kiện mạng đặc msbình,Trễ trung trưng. Tải của các lớp lưu lượng trên mỗi liên kết được tạo 100 500 900 ra bằng cách ấn định số lượng của lưu lượng nguồn ON- 1300 1700 2100 2500 2900 3300 3700 4100 4500 4900 OFF trong từng lớp lưu lượng của liên kết. Nhóm dữ liệu Bảng I. Mô hình lưu lượng của các lớp lưu lượng và tải Trễ mạng Trễ dự báo trọng trên các liên kết Hình 1. Dự báo trễ trung bình với nhóm tin K=1000. Lớp Mô hình lưu lượng Tải Tải Tải lưu trên trên trên Tỉ lệ trễ đầu cuối vượt ngưỡng cho trước DQoS = lượng Loại Độ dài Độ dài liên liên liên 100ms trong nhóm K=1000 gói tin được dự báo theo (15) phân trung trung kết 1 kết 2 kết 3 cũng cho các kết quả khả quan, với tỉ lệ trễ vượt ngưỡng bố bình bình và 5 và 4 (%) trung bình thống kê trong một khoảng thời gian đủ lớn (ví chu kì chu kì (%) (%) ON OFF dụ như trong trường hợp mô phỏng, trên 5 triệu gói tin (ms) (ms) tương ứng độ dài khoảng 200 s của luồng lưu lượng 100 Mbps) là 21% đối với tỉ lệ thực tế và 24.37% cho kết quả 1 Pareto 1.0 100 7,92 7,43 6,19 dự báo. Với mục tiêu đảm bảo trễ đầu cuối cho các luồng 2 Pareto 1.0 50 15,69 14,71 12,25 và ứng dụng thích ứng kịp thời với sự thay đổi của trạng thái, tỉ lệ trễ vượt ngưỡng cũng được quan trắc liên tục cho 3 Pareto 2.0 300 5,3 4,97 4,14 từng khoảng thời gian nhỏ, (ví dụ cho từng nhóm 1000 gói tin, tương đương độ dài luồng 100 Mbps trung bình 40 ms). 4 Pareto 2.0 200 7,92 7,43 6,19 Kết quả quan sát cho một đoạn dữ liệu điển hình mô tả 5 Hàm 1.0 100 7,92 7,43 6,19 trong Hình 2. mũ Có thể thấy với các nhóm gói tin không lớn, tỉ lệ trễ 6 Hàm 10.0 400 19,51 18,29 15,24 vượt một ngưỡng xác định biến thiên liên tục và ngẫu mũ nhiên, trong một dải rộng từ 0 đến 1.0. Hiện tượng trễ đầu cuối gói tin vượt ngưỡng thường xảy ra liên tục trong một 7 Pareto 2.0 100 15,69 14,71 12,25 khoảng thời gian ngắn, ứng với thời điểm tắc nghẽn trên 8 Pareto 1.0 200 3,98 3,73 3,11 mạng. Tuy nhiên có thể thấy các thuật toán dự báo cũng đã
6. ĐỊNH TUYẾN QOS SỬ DỤNG THÔNG TIN NỘI BỘ ĐẢM BẢO TRỄ END-TO-END đạt được tính thích nghi tức thời, ước lượng khá sát được các điểm xảy ra tắc nghẽn và xu hướng biến thiên của tỉ lệ Hiệu năng định tuyến QoS trễ vượt giá trị cho trước. Điều này khẳng định độ tin cậy của công cụ dự báo và có thể đóng vai trò như một chỉ báo tắc nghẽn trên đường định tuyến, hỗ trợ cho quá trình đảm 1 bảo chất lượng dịch vụ. 0.8 Tỉ lệ trễ vượt ngưỡng 100ms 0.6 0.4 1.2 0.2 1 0 0.8 1000 2000 3000 4000 5000 0.6 K Tỉ lệ Tỉ 0.4 lệcôngthànhtuyến địnhTỉ Định tuyến dựa trên đo trễ 0.2 0 Định tuyến dựa trên dự báo 101 161 221 281 341 401 461 521 581 641 701 761 821 881 941 Hình 3. Tính chính xác đảm bảo trễ đầu cuối của giải thuật Nhóm dữ liệu định tuyến QoS LDCQR-DP. Tỉ lệ thực tế Tỉ lệ dự báo Kết quả cho thấy giải thuật định tuyến đề xuất LDCQR- DP đạt hiệu năng định tuyến hơn hẳn so với phương pháp Hình 2. Dự báo tỉ lệ trễ vượt ngưỡng QoS cho nhóm gói truyền thống sử dụng bản tin đo trễ. Đặc biệt đối với định tin K=1000. tuyến cho các đoạn dữ liệu K nhỏ. Nguyên nhân xuất phát từ độ trễ của gói tin thử nghiệm (bằng RTT của mạng) khi C. Đánh giá tính chính xác đảm bảo trễ end-to-end của được sử dụng để đo hiện trạng tức thời mạng. Độ trễ này giải thuật LDCQR-DP càng lớn so với độ dài đoạn dữ liệu K gói tin thì sai lệch Đánh giá tỉ lệ đảm bảo trễ QoS trên tuyến được chọn khi đưa ra quyết định định tuyến cũng càng lớn. Từ đó có được thực hiện với yêu cầu giá trị trễ đầu cuối phải nhỏ hơn thể thấy hạn chế của phương pháp đo lường khi định tuyến giá trị cho trước, trong trường hợp thử nghiệm chọn với các luồng thời gian tồn tại ngắn, và được khắc phục bới 푄표푆 = 100 푠. Với mục đích đánh giá hiệu năng định phương pháp định tuyến đề xuất dựa trên ước lượng trễ đầu tuyến QoS, giải pháp định tuyến đề xuất LDCQR-DP cũng cuối. Có thể thấy độ chính xác của phương pháp dự báo được so sánh với giải thuật định tuyến QoS đảm bảo trễ giảm đi khi tăng độ dài đoạn dữ liệu, tuy nhiên giải pháp end-to-end truyền thống sử dụng các bản tin kiểm tra vẫn đạt được độ tin cậy cao. Giải thuật LDCQR-DP vì vậy [9,10]. Với các giải thuật này, tại thời điểm t, nút nguồn sử đảm bảo khả năng thích nghi với các độ dài luồng bất kì, dụng trễ tức thời đo được thông qua bản tin thử nghiệm. và sự thay đổi trạng thái mạng. Ngoài ra, giải thuật đề xuất Do độ trễ gửi và nhận gói tin qua mạng, gói tin thử nghiệm còn cho phép sử dụng các chỉ tiêu QoS khác mà các giải phải được gửi trước thời điểm t một khoảng thời gian xấp thuật đo lường đánh giá trễ bị hạn chế, như biến thiên trễ, xỉ RTT của mạng. Trong trường hợp này, trễ gói tin thử tỉ lệ trễ vượt ngưỡng, nghiệm được lấy bằng 160ms. Hai phương pháp định tuyến đảm bảo trễ đầu cuối được đánh giá qua xác suất định tuyến VI. KẾT LUẬN thành công, tức là tỉ lệ quyết định định tuyến đúng của giải Trong bài báo này các tác giả đề xuất giải thuật định thuật định tuyến QoS, dựa trên trễ đầu cuối thực tế có đáp tuyến QoS sử dụng thông tin nội bộ LDCQR-DP. Điểm ứng được yêu cầu trễ 푄표푆 trên tuyến đường đã được chọn mới quan trọng trong giải thuật đề xuất là áp dụng phương hay không (Hình 3). pháp dự báo trễ đầu cuối thông qua phân tích phân bố cũng như các tham số của giá trị trễ cực đại. Phương pháp cho phép tính toán trễ thích nghi cho bất cứ luồng lưu lượng với độ dài linh hoạt, đảm bảo tính chính xác cũng như độ phức tạp giải thuật, và do đó có khả năng ứng dụng trên mạng Internet thực tế. Giải thuật LDCQR-DP là cơ sở để thực hiện các giải pháp đảm bảo QoS theo yêu cầu cho các ứng dụng, đặc biệt là các ứng dụng đa phương tiện, đòi hỏi đáp ứng nghiêm ngặt các chỉ tiêu về thời gian truyền dẫn, bao gồm cả trễ trung bình, biến thiên trễ, hay tỉ lệ trễ vượt giới hạn, trong các khoảng thời gian yêu cầu khác nhau. Giải pháp đề xuất cho phép xác định trước các tham số QoS của luồng dữ liệu mà không cần xem xét đến lưu lượng hay hiện trạng mạng, khắc phục được một trong những tồn tại của các giải thuật định tuyến QoS truyền thống. Đồng thời, LDCQR-DP còn đơn giản hóa quá trình định tuyến và độ trễ định tuyến, không cần phải thực hiện đo đánh giá chất lượng tuyến được chọn, giảm lưu lượng gửi bản tin điều khiển định tuyến mạng.
7. Nguyễn Chiến Trinh, Nguyễn Thị Thu Hằng Đề xuất định tuyến QoS sử dụng thông tin nội bộ [16]. E. Castillo, “Extreme Value Theory in Engineering.” LDCQR-DP phù hợp với các mô hình định tuyến tập trung Academic, New York (1998). và định tuyến end-to-end theo xu thế của mạng thế hệ mới, [17]. J. Qiu and E.W. Knightly, “Interclass resource sharing như công nghệ SDN, MPLS. Trên cơ sở các kết quả đạt using statistical service envelopes” in Proc. INFOCOM 99, được, hướng nghiên cứu tiếp theo là xây dựng mô hình định Mar. 1999, pp. 1404-1411. tuyến QoS với các yêu cầu đa dạng về trễ đầu cuối, cũng [18]. J. Qiu and E.W. Knightly, “Measurement-based admission như mở rộng các yêu cầu khác về tính tin cậy, thông lượng. control with aggregate traffic envelopes” IEEE/ACM Trans. Networking, vol.9, no. 2, Apr. 2001, pp. 199-210. TÀI LIỆU THAM KHẢO [19]. S. Haykin, “Modern Filter.” New York: Macmillan (1989). [1]. E. Marilly, et all., “Service level agreements: a main LOCALIZED QOS ROUTING TO GUARANTEE challenge for next generations networks,” 2nd European END-TO-END DELAY Conference on Universal Multiservice Networks. ECUMN'2001, pp. 297-304. Abstract: A QoS routing algorithm to guarantee end-to- [2]. S. Nelakuditi, et all., “On localized control in QoS routing,” end delay metrics for real time applications, especially Automatic Control, IEEE Transactions on., vol. 47 (2002), multimedia, is an important issue supporting Quality of pp. 1026-1034. Service (QoS) over Internet. Recently, localized QoS [3]. S. Nelakuditi, Z. L. Zhang, R. Tsang and D. Du, “On routing has been proposed as a promising alternative to the selection of candidate paths for proportional routing,” deployed global QoS routing algorithms. This approach Computer networks, vol. 44 (2004), pp. 79-102. significantly reduces the overheads associated with [4]. S. Nelakuditi, Z. L. Zhang, R. Tsang and D. Du, “Adaptive Proportional Routing: a Localized QoS Routing maintaining global states at each node, which in turn Approach”, IEEE/ACM Transactions on Networking, vol. improves the overall routing performance. Routing with 10 (2002), pp. 790-804. delay guarantee involves path-constrained requirements, [5]. S. Alabbad, M. E. Woodward, “Localized Credit Based which are harder and more complex to satisfy than routing Routing: Performance Evaluation Using Simulation", Proc. with bandwidth guarantee, which involves only link- of IEEE 39th Annual Simulation Symposium, Huntsville, constrained requirements. In this paper, we introduce a Al. USA (2006). Localized Delay-Constrained QoS Routing algorithm [6]. T. A. Al Ghamdi and M. E. Woodward, "Novel localized using Delay Prediction (LDCQR-DP), which can QoS routing algorithms," in Proc. IEEE 9th Malaysia guarantee end-to-end delay requirements over any runtime International Conference on Communications, Kuala Lumpur, Malaysia, Dec. 2009, pp. 199-204. of flows. Simulation results have shown high accuracy of [7]. T. A. Al Ghamdi and M. E. Woodward, "Novel algorithms delay guarantee and considerable routing performance for QoS localized routing in communication networks," in improvement achieved by the proposed QoS routing Proc. First Asian Himalayas International Conference on algorithm. Internet, Kathmandu, Nepal, Nov. 2009, pp. 1-7. Keyword: QoS routing, End-to-end delay, Localized [8]. F. M. Aldosari, “Localized QoS Routing Based on Links routing, Delay prediction. Blocking Probability,” in Proc. 11th International Conference on Information Technology: New Generations Nguyễn Chiến Trinh nhận (2014), pp. 207-213. học vị Tiến sĩ Kỹ thuật tại [9]. Minh Anh Tran, Chien Trinh Nguyen, “A new localized Trường Điện – Thông tin multi-constraint QoS routing algorithm”. Journal of Tôkyô, Nhật bản năm 2005. Research, Development on Information and Hiện nay đang công tác tại Communications Technology, Vietnam Ministry of Khoa Viễn thông 1, Học Information and Communications Technology, Volume E– 3, Number 14, Sep. 2017, pp. 34-44. viện Công nghệ Bưu chính [10]. F. M. Aldosari and F. Alradady, "Localized QoS Routing Viễn thông. Các lĩnh vực with End-to-End Delay Guarantees," in Proc. International nghiên cứu: điều khiển lưu Conference on Information Technology: New Generations, lượng, định tuyến QoS, đảm Las Vegas, NV, April 2013, pp. 464-472. bảo QoS mạng IP, SDN, [11]. A. Popescu and D. Constantinescu, “Modeling of One-way WSN, transit time for IP Router,” Proceeding of the Advanced Email:trinhnc@ptit.edu.vn International Conference on Telecommunications and International Conference on Internet and Web Applications Nguyễn Thị Thu Hằng and Services AICT-ICIW’06, Feb. 2006. [12]. C. J. Bovy, H. T. Mertodimedjo, G. Hooghemstra, H. nhận học vị Tiến sĩ tại Học Uijterwaal, and P. Van Mieghem, “Analysis of end-to-end viện Công nghệ Bưu chính delay measurement in Internet”, In Proceeding of PAM Viễn thông (PTIT) Việt 2002, Mar. 2002. Nam năm 2020. Hiện nay [13]. M. E. Crovella and A. Bestavros, “Self-similarity in World là giảng viên Khoa Viễn Wide Web traffic: Evidence and posible causes”, thông 1-PTIT. IEEE/ACM Transactions on Networking, Vol. 5, No. 6, Các lĩnh vực nghiên cứu Dec. 1997, pp. 835-846. chính: Mạng truyền thông, [14]. V. Paxson and S. Floyd, “Wide Area Traffic: The failure of mạng cảm biến, mô phỏng Poisson modeling”, IEEE/ACM Transactions on Networking, Vol. 3, No. 3, June 1995, pp. 226-244. định tuyến QoS và giao [15]. W. E. Leland, M. S. Taqqu, W. Willinger and D. V. Wilson, thức lớp MAC. “On the self-similar nature of Ethernet traffic (Extended Email: version)”, IEEE/ACM Trans. Networking 2 (1) (1994), pp. hangntt@ptit.edu.vn 1-15.