Luận án: Giải quyết bài toán định tuyến đảm bảo băng thông độ trễ của NCS Cao Thái Phương Thanh

Giải pháp tối ưu hóa bài toán định tuyến mạng đảm bảo băng thông và độ trễ. Phân tích chi tiết các thuật toán QoS và mô hình điều phối lưu lượng hiệu quả.

• Tác giả: Cao Thái Phương Thanh
• Người hướng dẫn: PGS. Trần Công Hùng
• Trường học: Học viện Công nghệ Bưu chính Viễn thông
• Chuyên ngành: Hệ thống thông tin
• Đề tài: Giải quyết bài toán định tuyến đảm bảo băng thông, độ trễ
• Loại tài liệu: Luận án tiến sĩ kỹ thuật
• Năm xuất bản: 2017
• Địa điểm: Hà Nội

Tóm tắt

I. Tổng quan về bài toán định tuyến đảm bảo băng thông độ trễ

Bài toán định tuyến đảm bảo chất lượng dịch vụ QoS đóng vai trò then chốt trong hạ tầng mạng hiện đại. Luận án tiến sĩ năm 2017 tại Học viện Công nghệ Bưu chính Viễn thông PTIT đã nghiên cứu chuyên sâu về chủ đề này. Hệ thống mạng viễn thông ngày nay đối mặt với khối lượng dữ liệu khổng lồ. Các dịch vụ đa phương tiện thời gian thực như thoại VoIP, truyền hình hội nghị và video trực tuyến đòi hỏi đường truyền ổn định. Kỹ thuật định tuyến truyền thống chỉ tập trung vào tiêu chí đường đi ngắn nhất. Tiêu chí này dẫn đến hiện tượng tắc nghẽn trên các liên kết trọng yếu. Việc bổ sung đồng thời hai tham số băng thông và độ trễ giúp khắc phục triệt để nhược điểm trên. Mỗi yêu cầu kết nối unicast được mô hình hóa rõ ràng qua các giá trị ngưỡng. Thuật toán tìm kiếm đường đi khả thi đáp ứng cả hai điều kiện cùng lúc. Quá trình phân bổ tài nguyên diễn ra linh hoạt theo trạng thái mạng. Nghiên cứu mang lại nền tảng lý thuyết vững chắc cho bài toán tối ưu hóa mạng chuyển mạch gói.

1.1. Khái niệm định tuyến đảm bảo chất lượng dịch vụ QoS

Chất lượng dịch vụ QoS thể hiện mức độ cam kết của nhà mạng đối với lưu lượng truyền tải. Khái niệm này bao gồm nhiều độ đo kỹ thuật như băng thông, độ trễ, độ rung pha và tỷ lệ mất gói. Trong mạng máy tính, định tuyến QoS là quá trình tìm kiếm đường đi thỏa mãn các ràng buộc định trước. Nút mạng thu thập trạng thái tài nguyên của từng liên kết kết nối. Khi xuất hiện lưu lượng mới, hệ thống tính toán tuyến truyền tối ưu. Cơ chế kiểm soát chấp nhận đánh giá tính khả dụng của tài nguyên mạng. Nếu tài nguyên không đủ, hệ thống sẽ từ chối để tránh suy giảm chất lượng dịch vụ hiện có. Ngược lại, mạng cấp phát tài nguyên tức thì cho kết nối hợp lệ.

1.2. Mô hình bài toán định tuyến Unicast tại PTIT 2017

Nghiên cứu của tác giả Cao Thái Phương Thanh tại PTIT năm 2017 xây dựng bài toán unicast chi tiết. Một yêu cầu kết nối r được đặc trưng bởi bộ tham số nguồn s, đích d, băng thông yêu cầu và ngưỡng trễ. Mạng truyền thông được biểu diễn dưới dạng đồ thị có hướng. Các đỉnh đại diện cho nút mạng và các cung đại diện cho liên kết vật lý. Mỗi liên kết sở hữu dung lượng truyền dẫn và độ trễ cố định hoặc phụ thuộc tải. Thuật toán tìm đường đi từ nguồn đến đích sao cho mọi liên kết đều đáp ứng băng thông khả dụng. Đồng thời, tổng thời gian trễ của đường đi không được vượt quá ngưỡng trễ quy định. Mô hình toán học này phản ánh chính xác hoạt động của mạng viễn thông thực tế.

II. Phân tích thách thức định tuyến đảm bảo băng thông độ trễ

Định tuyến đa ràng buộc là bài toán thuộc lớp NP-khó trong lý thuyết đồ thị. Khi kết hợp tiêu chí băng thông và độ trễ, mức độ phức tạp tính toán tăng lên đáng kể. Băng thông có tính chất thắt nút cổ chai (bottleneck metric), phụ thuộc vào liên kết có dung lượng nhỏ nhất trên tuyến. Ngược lại, độ trễ có tính chất cộng dồn (additive metric), bằng tổng độ trễ của tất cả liên kết đi qua. Sự khác biệt về bản chất toán học giữa hai thuộc tính gây khó khăn lớn cho việc tối ưu hóa. Thiết lập một đường đi mới sẽ làm giảm băng thông khả dụng của toàn mạng. Điều này ảnh hưởng trực tiếp đến khả năng tiếp nhận các luồng dữ liệu tiếp theo. Nếu lựa chọn đường đi không hợp lý, các liên kết quan trọng nhanh chóng cạn kiệt tài nguyên. Hiện tượng phân mảnh băng thông xuất hiện làm tăng tỷ lệ từ chối yêu cầu. Ngoài ra, việc xác định trạng thái tải mạng động cũng rất phức tạp. Tần suất đến ngẫu nhiên của các yêu cầu tạo ra biến động tải liên tục trên hệ thống.

2.1. Bản chất toán học của các ràng buộc băng thông và độ trễ

Sự kết hợp giữa thuộc tính cộng dồn và thắt nút tạo ra thách thức lớn. Băng thông còn lại của đường đi được định nghĩa bằng giá trị cực tiểu của các liên kết thành phần. Thuật toán có thể loại bỏ ngay các liên kết không đủ băng thông trước khi tìm kiếm. Tuy nhiên, độ trễ tích lũy lại tăng dần theo số lượng chặng truyền dẫn. Đường đi có ít chặng chưa chắc đã có độ trễ nhỏ nhất. Ngược lại, đường đi vòng qua nhiều liên kết có thể tích lũy độ trễ vượt ngưỡng. Sự xung đột này khiến thuật toán Dijkstra tiêu chuẩn không thể áp dụng trực tiếp. Các giải pháp quy hoạch tuyến tính truyền thống cũng đòi hỏi chi phí tính toán rất cao. Hệ thống cần các kỹ thuật heuristic linh hoạt để tìm lời giải gần tối ưu.

2.2. Vấn đề biến động tài nguyên trong kịch bản tải động

Trong môi trường thực tế, lưu lượng mạng thay đổi liên tục theo thời gian. Các yêu cầu kết nối xuất hiện ngẫu nhiên và giải phóng băng thông sau khi hoàn thành phiên truyền. Điều này tạo ra sự khác biệt lớn giữa mô hình định tuyến tĩnh và động. Ở điều kiện tải thấp, lượng băng thông yêu cầu không vượt quá ba mươi phần trăm tổng dung lượng. Mạng dễ dàng tìm được tuyến truyền phù hợp mà không gây tắc nghẽn. Tuy nhiên, khi tải vượt ngưỡng bảy mươi phần trăm, mạng rơi vào trạng thái quá tải nghiêm trọng. Số lượng yêu cầu tăng vọt cùng tốc độ gửi tin dồn dập khiến băng thông cạn kiệt. Nếu không có thuật toán tối ưu, tỷ lệ từ chối sẽ gia tăng nhanh chóng.

III. Phương pháp giải bài toán định tuyến đảm bảo băng thông độ trễ

Để giải quyết triệt để bài toán, luận án đã khảo sát và cải tiến nhiều thuật toán tiên tiến. Ba nhóm phương pháp chính được tập trung phân tích gồm: nhóm dựa trên thông số liên kết, nhóm hạn chế ảnh hưởng đến các luồng tương lai và nhóm ứng dụng máy học. Các thuật toán tiêu biểu như LDA, MDWCRA và MDMF được đưa vào đánh giá so sánh. Thuật toán LDA tập trung tối ưu hóa hàm mục tiêu kết hợp băng thông và độ trễ. MDWCRA tính toán trọng số liên kết dựa trên năng lực phục vụ còn lại. MDMF áp dụng nguyên lý luồng cực đại để tránh tắc nghẽn sớm. Trước tiên, hệ thống thực hiện cắt lọc đồ thị nhằm loại bỏ liên kết thiếu băng thông. Sau đó, thuật toán áp dụng hàm chi phí để chọn tuyến có độ trễ nhỏ nhất. Kỹ thuật cân bằng tải giúp phân tán lưu lượng đồng đều trên toàn bộ mạng. Kết quả mô phỏng chứng minh giải pháp đề xuất cải thiện rõ rệt hiệu năng hệ thống.

3.1. Các thuật toán định tuyến LDA MDWCRA và MDMF

Thuật toán LDA (Link Delay and Availability) xem xét đồng thời độ trễ và tính khả dụng của liên kết để định hình tuyến truyền. Phương pháp này gán trọng số thích nghi dựa trên mức tiêu hao tài nguyên. Thuật toán MDWCRA (Multi-Constrained Dynamic Worst-Case Routing Algorithm) mở rộng bài toán sang trường hợp xấu nhất nhằm giảm thiểu xung đột tài nguyên trong tương lai. Kỹ thuật này ngăn chặn việc sử dụng các liên kết hiểm yếu khi mạng còn nhiều đường vòng thay thế. Thuật toán MDMF (Multi-Constrained Delay Maximum Flow) kết hợp bài toán luồng cực đại đa ràng buộc để tối đa hóa dung lượng truyền tải. Cả ba thuật toán đều cung cấp cơ chế kiểm soát chất lượng dịch vụ chặt chẽ. Hiệu quả thuật toán được chứng minh qua khả năng bảo toàn băng thông cho mạng.

3.2. Quy trình kiểm tra và thiết lập đường truyền tối ưu

Quy trình xử lý một yêu cầu định tuyến bắt đầu từ nút nguồn s. Hệ thống tiến hành thu thập thông tin cấu hình mạng và thông số liên kết hiện tại. Các liên kết có băng thông khả dụng nhỏ hơn giá trị yêu cầu bị lược bỏ ngay lập tức khỏi đồ thị tính toán. Trên đồ thị con đã thu gọn, thuật toán thực hiện tìm kiếm tuyến có tổng độ trễ nhỏ hơn ngưỡng δ cho phép. Nếu tìm thấy ít nhất một đường đi thỏa mãn, yêu cầu được chấp nhận. Băng thông khả dụng của các liên kết trên tuyến đó lập tức giảm đi một lượng b. Ngược lại, nếu không có đường đi nào thỏa mãn cả hai điều kiện, yêu cầu bị từ chối. Quy trình này bảo đảm không phá vỡ cam kết chất lượng của các luồng đang hoạt động.

IV. Ứng dụng thực tiễn định tuyến đảm bảo băng thông độ trễ mạng

Kết quả nghiên cứu của luận án tiến sĩ tại PTIT năm 2017 mang tính ứng dụng thực tiễn cao cho mạng viễn thông. Các thuật toán được kiểm nghiệm nghiêm ngặt thông qua mô phỏng trên các cấu trúc mạng chuẩn như MIRA, ANSNET và CESNET. Kịch bản thử nghiệm đa dạng từ 2000 yêu cầu ở điều kiện tải bình thường đến 5000 yêu cầu ở điều kiện tải cao. Kết quả cho thấy thuật toán tối ưu giúp giảm đáng kể tỷ lệ từ chối yêu cầu kết nối. Băng thông mạng được khai thác triệt để mà không gây hiện tượng nghẽn mạch cục bộ. Độ trễ trung bình của các gói tin được duy trì ổn định dưới ngưỡng cho phép. Mô hình này rất phù hợp để triển khai trên các mạng lõi chuyển mạch nhãn đa giao thức MPLS và mạng điều khiển bằng phần mềm SDN. Hạ tầng mạng của các nhà mạng có thể ứng dụng trực tiếp thuật toán để nâng cao chất lượng dịch vụ và tối ưu hóa chi phí vận hành.

4.1. Đánh giá hiệu năng trên các sơ đồ mạng thực nghiệm

Nghiên cứu sử dụng các bộ sơ đồ mạng nổi tiếng thế giới để đo đạc và kiểm chứng thuật toán. Sơ đồ MIRA mô phỏng mạng lõi với các liên kết dung lượng cao 4800 đơn vị OC. Sơ đồ ANSNET và CESNET đại diện cho mạng đường trục quốc gia và khu vực với cấu trúc liên kết phức tạp. Trong các thử nghiệm tĩnh, hệ thống đánh giá khả năng tiếp nhận yêu cầu với dung lượng từ một đến ba đơn vị băng thông. Ở điều kiện tải cao trên bảy mươi phần trăm, thuật toán đề xuất vượt trội so với các giải pháp truyền thống. Khả năng cân bằng tải trên các liên kết giúp hệ thống duy trì tính ổn định. Tỷ lệ phục vụ thành công đạt mức tối ưu trên toàn bộ các kịch bản kiểm thử.

4.2. Khả năng tích hợp vào mạng SDN và thế hệ mới

Kiến trúc mạng điều khiển bằng phần mềm SDN tạo môi trường lý tưởng để triển khai thuật toán định tuyến QoS. Bộ điều khiển trung tâm SDN có tầm nhìn toàn cục về trạng thái băng thông và độ trễ của mọi liên kết vật lý. Khi nhận được yêu cầu kết nối từ ứng dụng, bộ điều khiển kích hoạt thuật toán để tính toán đường đi tức thì. Các luồng lưu lượng được cài đặt linh hoạt vào bảng chuyển tiếp của thiết bị chuyển mạch OpenFlow. Sự kết hợp này giúp nhà mạng phản ứng linh hoạt trước biến động tải đột ngột. Đồng thời, chất lượng dịch vụ của các ứng dụng nhạy cảm trễ được bảo đảm tuyệt đối. Nghiên cứu mở ra hướng đi đầy tiềm năng cho mạng viễn thông thế hệ tương lai.

Trích đoạn nội dung tài liệu

phần Mở đầu, luận án nghiên cứu vấn đề định tuyến unicast. • Định tuyến broadcast: dữ liệu được truyền từ một nút nguồn đến tất cả nút khác trong mạng. Broadcast chủ yếu được dùng để cập nhật thông tin hoạt động của hệ thống mạng. • Định tuyến multicast: dữ liệu được truyền từ một nút nguồn đến một số nút đích, các nút đích này có thể thay đổi trong quá trình định tuyến.

Multicast thường áp dụng cho các dịch vụ làm việc theo nhóm, xem truyền hình trực tuyến theo yêu cầu [71]. Ngoài ra thuật toán định tuyến còn được phân loại theo một số tiêu chí khác. Dựa trên thời điểm xác định đường đi, có hai loại: định tuyến theo yêu cầu và định tuyến chủ động. Định tuyến theo yêu cầu xác định đường đi khi nhận được yêu cầu thiết lập kết nối.

Vì dựa trên các thông số động của hệ thống (tại thời điểm nhận yêu cầu) nên đường đi được xác định một cách linh hoạt giúp tăng hiệu quả hoạt động mạng. Ngược lại, đối với định tuyến chủ động, thời điểm xác định và thiết lập đường đi không liên quan đến yêu cầu kết nối. Vì vậy, thời gian đáp ứng của định tuyến chủ động nhanh nhưng khó đảm bảo yêu cầu chất lượng dịch vụ [2]. Định tuyến còn được phân loại dựa trên cách thức tìm đường: • Định tuyến tập trung: việc xác định đường đi được thực hiện tại nút nguồn hoặc một thiết bị mạng có khả năng thích hợp (gọi chung là thiết bị tìm đường).

Thông tin trạng thái của hệ thống được cập nhật và duy trì tại mỗi thiết bị tìm đường. Sau khi xác định được đường đi, thiết bị tìm đường sẽ gửi thông điệp điều khiển đến các nút mạng khác để thiết lập kết nối. Định tuyến tập trung có ưu điểm đơn giản, ít thông điệp điều khiển, dễ thực thi, và tránh được hiện tượng lặp 10 vòng. Mặt khác, định tuyến tập trung đòi hỏi thiết bị mạng, đặc biệt là thiết bị tìm đường có khả năng lưu trữ và xử lý cho toàn mạng, nên khó áp dụng trên hệ thống lớn.

Ngoài ra, vấn đề cập nhật thông tin trạng thái sao cho kịp thời nhưng tiết kiệm tài nguyên cũng là vấn đề khó [44]. • Định tuyến phân tán: việc xác định đường đi được thực hiện bằng cách chuyển tiếp các thông điệp tín hiệu giữa các nút mạng, mỗi nút chỉ quyết định đường đi đến một / một số nút kế tiếp thay vì tính toán toàn bộ đường đi. Điều này giúp cho thời gian thiết lập kết nối của định tuyến phân tán nhỏ, áp dụng được cho hệ thống mạng lớn. Tuy nhiên, vấn đề lặp vòng và khóa chết (deadlock) là những khó khăn khi thực thi định tuyến phân tán.

Tương tự như định tuyến tập trung, phần lớn các thuật toán định tuyến phân tán cũng yêu cầu cập nhật thông tin trạng thái hệ thống cho mỗi nút mạng [5]. • Định tuyến phân cấp: được đề xuất để áp dụng cho hệ thống mạng lớn, định tuyến phân cấp chia các nút mạng theo nhóm và mỗi nút chỉ duy trì thông tin trạng thái của nhóm thay vì toàn hệ thống. Việc chia nhóm này có thể được lặp lại tạo thành hệ thống phân cấp giúp giảm đáng kể lượng thông tin cần cập nhật. Khuyết điểm của định tuyến phân cấp là thông tin trạng thái có thể bị tổng hợp sai lệch ảnh hưởng xấu đến kết quả định tuyến [37].3 Một số hướng nghiên cứu phổ biến Từ những thuật toán định tuyến "best effort" ban đầu xác định đường đi tốt là đường đi ngắn nhất (qua ít nút mạng nhất) và chưa quan tâm đến chất lượng dịch vụ, đã có rất nhiều công trình nghiên cứu, đề xuất, cải tiến liên quan đến vấn đề định tuyến.

Một hướng nghiên cứu phổ biến là định tuyến nhiều đường (multipath routing) với mục tiêu hỗ trợ cân bằng tải và cung cấp đường đi dự phòng [51]. Ví dụ, các tác giả của [46] đã đề xuất một thuật toán phân tán tìm hai đường đi không có điểm chung cho mỗi cặp nút nguồn đích. Gần đây, thuật toán này được cải tiến để giảm thời gian tìm đường trong công trình [69]. Bên cạnh việc tìm đường đi không có điểm chung, đã có nhiều tác giả nghiên cứu thuật toán định tuyến tìm k đường đi cho mỗi cặp nút nguồn đích [55, 20, 78].

Một hướng nghiên cứu phổ biến khác là định tuyến tối ưu theo trọng số (hay chi phí) của liên kết. Trọng số này có thể được gán theo nhu cầu của nhà cung cấp mạng hoặc được tổng hợp từ các thông tin trạng thái như băng thông, độ trễ [66]. Nhiều 11 phương pháp tiếp cận đã được áp dụng cho định tuyến tối ưu, bao gồm thuật toán di truyền [34], tính toán tiến hóa [52], và phương pháp ước lượng [50]. Với yêu cầu tối ưu chi phí trong lĩnh vực mạng máy tính, vấn đề này đang nhận được nhiều sự quan tâm nghiên cứu.

Tương tự như định tuyến tối ưu theo trọng số, định tuyến đảm bảo chất lượng dịch vụ cũng là một vấn đề quan trọng của khoa học mạng máy tính. Trong định tuyến đảm bảo chất lượng dịch vụ, yêu cầu đầu tiên là đường đi tìm được phải thỏa ràng buộc chất lượng. Sau đó tùy theo mục tiêu phục vụ của công trình nghiên cứu mà thuật toán được đánh giá bằng những độ đo khác nhau. Mục kế tiếp trình bày chi tiết về các ràng buộc và mục tiêu của định tuyến đảm bảo chất lượng dịch vụ.3 ĐỊNH TUYẾN ĐẢM BẢO CHẤT LƯỢNG DỊCH VỤ Các độ đo chất lượng dịch vụ phổ biến bao gồm: • Băng thông: là số lượng dữ liệu có thể truyền đi trong một đơn vị thời gian, đơn vị tính ví dụ kilo bit trên giây (kb/s).

• Độ trễ: là khoảng thời gian truyền dữ liệu phụ thuộc vào thời gian truyền qua liên kết vật lý, thời gian xử lý của thiết bị mạng, thời gian trong hàng đợi. • Độ biến thiên trễ: là sự khác nhau giữa độ trễ của các gói tin. Độ biến thiên trễ phát sinh chủ yếu do thiết bị mạng cần xử lý truyền nhiều gói tin của nhiều luồng dữ liệu khác nhau. • Tỉ lệ mất gói: là tỉ lệ giữa số gói tin bị mất (bị lỗi, bị hủy) trên tổng số gói tin.

Các độ đo này có đặc tính khác nhau nên cách kiểm tra chất lượng dịch vụ trên đường truyền cũng khác nhau. Cụ thể, băng thông đường truyền là giá trị cực tiểu băng thông các liên kết (tính bằng phép cực trị); độ trễ đường truyền là tổng độ trễ khi dữ liệu đi qua các liên kết (tính bằng phép cộng), tỉ lệ mất gói được tính từ tỉ lệ truyền gói tin thành công bằng phép nhân các tỉ lệ thành công trên liên kết. Một số độ đo chất lượng dịch vụ như độ biến thiên trễ, tỉ lệ mất gói chỉ được xác định chính xác khi hệ thống đã có dữ liệu. Tuy nhiên, định tuyến đảm bảo chất lượng dịch vụ cần kiểm tra điều kiện ràng buộc, thiết lập kết nối trước khi truyền dữ liệu và đảm bảo điều kiện này được duy trì trong quá trình truyền.

Vì vậy, băng thông - với khả năng được xác định và được dành riêng một cách rõ ràng - trở thành ràng buộc chất lượng dịch vụ phổ biến nhất trong thuật toán định tuyến. Ngoài ra, các tác giả của [22, 27] cũng đã đề cập tới khả năng chuyển đổi một số giá trị độ đo khác sang 12 giá trị băng thông. Bên cạnh băng thông, dịch vụ mạng thế hệ mới, nhất là dịch vụ có tính tương tác cao như trò chơi, truyền hình trực tuyến còn quan tâm đến điều kiện độ trễ vì giá trị này quyết định thời gian đáp ứng dịch vụ. Trong bài toán định tuyến có đảm bảo độ trễ, giá trị độ trễ có thể giả sử là một thông số được biết trước của liên kết [67, 75], hoặc được tính theo lượng băng thông đảm bảo cho đường truyền [59].

Mục tiêu của thuật toán định tuyến đảm bảo chất lượng dịch vụ không chỉ là tìm được đường đi thỏa ràng buộc chất lượng mà còn phục vụ cho nhu cầu của nhà cung cấp mạng. Đối với định tuyến unicast, nhu cầu này là đáp ứng tối đa số yêu cầu định tuyến nên giải pháp định tuyến unicast được so sánh, đánh giá dựa trên số lượng yêu cầu được chấp nhận [22, 27, 47]. Đối với định tuyến multicast, bên cạnh nhu cầu tăng khả năng thiết lập kết nối, nhà cung cấp mạng còn mong muốn xác định cây đường đi có trọng số (chi phí) nhỏ nhất. Vì vậy, các công trình định tuyến multicast không chỉ được đánh giá dựa trên số yêu cầu được chấp nhận [31, 73] mà còn dựa trên tổng trọng số của cây đường đi [72, 54, 79].4 KẾT CHƯƠNG Chương 1 trình bày tổng quan về yêu cầu chất lượng dịch vụ và vấn đề định tuyến trong lĩnh vực mạng máy tính và truyền dữ liệu.

Sau phần giới thiệu chất lượng dịch vụ, các yếu tố quan trọng có liên quan được đề cập gồm hai cơ chế thực hiện chất lượng dịch vụ IntServ [70] và DiffServ [10]; kĩ thuật chuyển mạch nhãn đa giao thức MPLS [17], và vấn đề định tuyến đảm bảo chất lượng dịch vụ. Trong đó, luận án quan tâm nghiên cứu nội dung định tuyến đảm bảo chất lượng dịch vụ.2 trình bày khái niệm định tuyến trong hệ thống mạng, chức năng của giao thức định tuyến và của thuật toán định tuyến, các tiêu chí phân loại và những hướng nghiên cứu định tuyến phổ biến hiện nay. Kế tiếp, độ đo chất lượng dịch vụ và yêu cầu mục tiêu của thuật toán định tuyến được giới thiệu trong mục 1. Luận án giải quyết bài toán định tuyến unicast đảm bảo băng thông và định tuyến đảm bảo băng thông, độ trễ.

Chương kế tiếp sẽ trình bày mô hình toán học của vấn đề, các công trình liên quan đã công bố, và môi trường thử nghiệm được sử dụng trong luận án. BÀI TOÁN ĐỊNH TUYẾN UNICAST ĐẢM BẢO BĂNG THÔNG VÀ ĐẢM BẢO BĂNG THÔNG, ĐỘ TRỄ 2.1 ĐỊNH NGHĨA BÀI TOÁN 2.1 Phát biểu bài toán và kí hiệu sử dụng Trong bài toán định tuyến, sơ đồ mạng được biểu diễn thành một đồ thị đơn có hướng G = (N, L) có tính liên thông yếu. Tập đỉnh của đồ thị N = {n0 , n1 , ., nk−1 } gồm k phần tử tương ứng với k nút mạng (thiết bị mạng tham gia vào quá trình định tuyến). Tập cạnh của đồ thị L = {l0 , l1 , ., lm−1 } gồm m phần tử tương ứng với m liên kết trong sơ đồ mạng.

Mỗi liên kết li = (nk , nh ) với nk , nh (k 6= h) ∈ N thể hiện nút nk có thể truyền dữ liệu trực tiếp đến nút nh .