Tiêu đề

GIẢI QUYẾT BÀI TOÁN ĐỊNH TUYẾN ĐẢM BẢO BĂNG
THÔNG, ĐỘ TRỄ

Tác giả

Cao Thái Phương Thanh

Chuyên ngành

Hệ thống thông tin

Nguồn phát hành

Học viện Công nghệ Bưu chính Viễn thông

Sơ lược

TRANG THÔNG TIN LUẬN ÁN TIẾN SĨ

Tên đề tài luận án tiến sĩ: GIẢI QUYẾT BÀI TOÁN ĐỊNH TUYẾN ĐẢM BẢO BĂNG
THÔNG, ĐỘ TRỄ

Chuyên ngành: Hệ thống thông tin

Mã số: 62.48.01.04

Họ và tên NCS: Cao Thái Phương Thanh

Người hướng dẫn khoa học:

1. PGS.TS. Trần Công Hùng

2. PGS. TS. Hà Hải Nam

Cơ sở đào tạo: Học viện Công nghệ Bưu chính Viễn thông

NHỮNG KẾT QUẢ MỚI CỦA LUẬN ÁN
1. Đề xuất thuật toán định tuyến đảm bảo băng thông BGHT sử dụng thời gian giữ băng thông của yêu cầu định tuyến, với điều kiện thời gian này được biết. Kết quả mô phỏng cho thấy BGHT có tỉ lệ chấp nhận yêu cầu cao hơn, trong khi thời gian tính toán trung bình thấp hơn các công trình liên quan.
2. Đề xuất thuật toán định tuyến đảm bảo băng thông TEARD sử dụng các thông tin từ hệ thống mạng và yêu cầu định tuyến đã nhận được. Thuật toán có tỉ lệ chấp nhận yêu cầu tốt hơn và thời gian tìm đường so sánh được với công trình liên quan.
3. Đề xuất thuật toán định tuyến đảm bảo băng thông và độ trễ HRABDC với phương pháp tính trọng số liên kết đơn giản và kĩ thuật tìm đường Dijkstra heuristic được nghiên cứu sinh cải tiến từ thuật toán Dijkstra cho bài toán tìm đường đảm bảo độ trễ. HRABDC không chỉ có tỉ lệ chấp nhận yêu cầu tốt hơn mà còn có thời gian tính trung bình thấp hơn rất nhiều so với các công trình liên quan.
4. Đề xuất thuật toán định tuyến đảm bảo băng thông và độ trễ eHRABDC bổ sung độ trễ vào công thức trọng số và áp dụng Dijkstra tăng cường heuristic nhằm cố gắng tìm đường đi có trọng số nhỏ. Thuật toán tìm được đường đi có trọng số nhỏ hơn HRABDC và trong nhiều thử nghiệm có tỉ lệ chấp nhận yêu cầu cao hơn. Về thời gian tìm đường, kết quả của eHRABDC tuy cao hơn HRABDC nhưng vẫn thấp hơn các thuật toán định tuyến liên quan khác.

5. Xây dựng chương trình mô phỏng để thử nghiệm, so sánh các thuật toán định tuyến đảm bảo chất lượng dịch vụ. Chương trình được cài đặt với kiến trúc mở, dễ dàng cài đặt thêm thuật toán hoặc mở rộng yêu cầu chất lượng. Toàn bộ mã nguồn chương trình bao gồm các thuật toán nghiên cứu sinh đã đề xuất và các thuật toán liên quan được công bố trên mạng Internet.

CÁC ỨNG DỤNG, KHẢ NĂNG ỨNG DỤNG TRONG THỰC TIỄN HOẶC NHỮNG VẤN ĐỀ CÒN BỎ NGỎ CẦN TIẾP TỤC NGHIÊN CỨU:
Khả năng ứng dụng trong thực tiễn
Các thuật toán đã đề xuất được ứng dụng trong giao thức định tuyến đảm bảo chất lượng dịch vụ, được triển khai trong hệ thống mạng của nhà cung cấp dịch vụ. Thuật toán định tuyến không chỉ giúp nhà cung cấp dịch vụ đảm bảo chất lượng dịch vụ đã cam kết với khách hàng mà còn giúp khai thác tối đa hệ thống mạng hiện có, tăng số lượng yêu cầu có thể đáp ứng cho khách hàng.
Những vấn đề còn bỏ ngỏ cần tiếp tục nghiên cứu
Triển khai các thuật toán định tuyến đã đề xuất cũng như một số thuật toán liên quan trên hệ thống mạng MPLS TE với máy chủ định tuyến và các giao thức đảm bảo yêu cầu bài toán. Từ đó tiến hành thử nghiệm, đánh giá, so sánh hiệu quả định tuyến của các thuật toán trên hệ
thống mạng thực tế.
Giải quyết bài toán multicast đảm bảo chất lượng dịch vụ với cùng mục tiêu tìm cây
đường đi cho mỗi yêu cầu định tuyến sao cho đáp ứng tối đa số yêu cầu nhận được.

Xác nhận của người hướng dẫn khoa học :

PGS.TS. Trần Công Hùng

Nghiên cứu sinh:

Cao Thái Phương Thanh

INFORMATION PAGE OF DOCTOR THESIS

Subject: SOLVING BANDWIDTH, DELAY GUARANTEED ROUTING PROBLEM

Speciality: Information system
Code: 62.48.01.04
Ph.D. candidate: Cao Thái Phương Thanh
Supervisor 1: Trần Công Hùng, Associate Professor, Ph.D.
Supervisor 2. Hà Hải Nam, Associate Professor, Ph.D.
Academic institute: Vietnam Posts and Telecommunications Institute of Technology

THESIS CONTRIBUTIONS
1. Propose a bandwidth guaranteed routing algorithm BGHT using holding time of routing requests. Simulated results show that BGHT has not only higher acceptance ratio but also lower computing time than related algorithms.
2. Propose a bandwidth guaranteed routing algorithm TEARD using routing data such as network topology and request probability. In experiments, TEARD has better performance compared to existing algorithms.
3. Propose a bandwidth and delay guaranteed routing algorithm HRABDC with a simple but effective link-weight calculation. Moreover, Dijkstra algorithm is modified to find a path with bandwidth delay constraints. Experimental acceptance ratio of HRABDC is comparable while its computing time is noticeably lower than other bandwidth, delay guaranteed routing solutions.
4. Enhance HRABDC by adding delay into link-weight as well as enhance the heuristic of finding path. The new algorithm called eHRABDC finds smaller weighs than HRABDC and in many case also has higher acceptance ratio. On the other hand, eHRABDC has longer computing time than HRABDC but still better than existing algorithms.
5. Develop a simulation program in order to experience and compare QoS routing algorithms. The program has open architecture which easily adds more algorithms as well as more QoS constraints. Source code of the program including proposed algorithms and related ones is published on the Internet.

APPLICATION AND FUTURE WORK
Application
Proposed algorithms are used in quality of service routing protocols as well as deployed in core, high-speed networks of service providers. Bandwidth, delay guaranteed routing algorithms are not only help to satisfy customer service-level agreements but also optimize network usage, increase number of accepted QoS requests.
Future work
Experiencing proposed algorithms against related ones in real MPLS TE networks in order to compare, evaluate routing performance. Solving QoS multicast routing problem which have the same objective of maximizing accepted QoS requests

Representer of advisors:

Assoc. Prof. Dr. Trần Công Hùng

Ph.D. candidate:

Cao Thái Phương Thanh

Tài liệu tham khảo