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