Phần mở đầu Lựa chọn nút đầu ra là một phần quan trọng của việc đánh giá QoS trong một mạng. Các tiếp cận truyền thống để giải quyết vấn đề này chỉ đem lại hiệu quả trong các mạng nhỏ, có ít luồng dữ liệu và ít các thay đổi cập nhật. Đối với một mạng lớn với số luồng luân chuyển cao, cách tiếp cận truyền thống bộc lộ các hạn chế, ví như thời gian hội tụ kéo dài. Xuất phát từ những hạn chế trong cách tiếp cận này, luận văn đề xuất một cách tiếp cận mới, sử dụng thuật toán học tăng cường để lựa chọn nút đầu ra một cách tối ưu.
Cách tiếp cận này dựa vào “phần thưởng” có được qua mỗi lần lựa chọn nút đầu ra để tính toán nút đầu ra đem lại phần thưởng lớn nhất. Do phần thưởng được tính toán dựa vào các tham số Loss và Delay, nén luận văn lựa chọn kiến trúc mạng SDN để thực hiện thực nghiệm, nơi mà SDN controller có cái nhìn tổng quan về topology mạng, có thê quản lý tập trung và lập trình trực tiếp được. Luận văn đề xuất bốn thuật toán để giải quyết bài toán MAB và đánh giá hiệu quả của từng thuật toán, qua đó nhận thấy thuật toán UCB là có hiệu quả hơn cả. Chương 2 Tổng quan Chương này trình bày về vấn đề lựa chọn nút biên và định tuyến liên miền.
Kiến trúc định tuyến two-tiered của Internet được thiết kế để có sự tách biệt rõ ràng giữa các giao thức định tuyến nội miền và liên miền. Tuy nhiên, vai trò thích hợp của hai giao thức trở nên không rõ ràng khi AS học các tuyến đường đến đích tại nhiều bộ định tuyến biên. Luận văn này cho rằng việc lựa chọn trong số nhiều điểm đầu ra hiện là một phần cơ bản của kiến trúc định tuyến Internet, không phụ thuộc vào bộ giao thức định tuyến hiện tại. Luận văn trình bày về cách tiếp cận truyền thống và các hạn chế của cách tiếp cận này như vấn đề không linh hoạt, dễ gây ra gián đoạn mạng và quá phức tạp cho các nhân viên quản trị mạng.
Phương pháp tiếp cận mới được đề xuất dựa trên thuật toán học tăng cường giúp phần nào cải thiện các hạn chế nêu trên. Chương 3 Đề xuất giải pháp lựa chọn nút đầu ra Chương này đề xuất giải pháp lựa chọn nút đầu ra dựa trên thuật toán học tăng cường. - Bài toán MAB: Để giới thiệu về bài toán MAB, đây là một vẫn đề học tăng cường cô điển minh họa cho tình thế khó khăn trong việc đánh đổi giữa thăm dò và khai thác. - Đề xuất sử dụng MAB trong bài toán lựa chọn nút đầu ra: Tìm ra sự tương đồng của việc lựa chọn nút đầu ra trong một mạng với bài toán MAB, từ đó đề xuất áp dụng MAB cho việc lựa chọn nút đầu ra mà ở đó, chung ta coi mỗi nút đầu ra tiềm năng là một “Hành động” (Acrion) và chỉ số QoS (công thức của độ trễ Delay và tỷ lệ mất mát gói tin Loss) là một “Phần thưởng” (Rewarđ).
Qua mỗi giai đoạn, Reward sẽ được lưu lại và thuật toán MAB sẽ sử dụng lịch sử của các reward tương ứng với mỗi nút đầu ra để chọn ra một nút đầu ra tối ưu nhất cho giai đoạn tiếp theo. - Đề xuất phương pháp đo Delay và Loss: Phần này giới thiệu các phương pháp mới khai thác các tính năng SDN và giao thức OpenFlow để tính toán tham số Delay và Loss trên các tuyến đường xác định giữa các bộ định tuyến. - Đề xuất thuật toán lựa chọn nút đầu ra dựa trên MAB: Trình bày bốn thuật toán thường dùng để giải quyết bài toán MAB là e-greedy, Softmax, UCBI và SP- UCB2. Chương 4 Kết quả thực hiện Chương này tập trung giải thích về các thành phan, giải pháp được sử dụng để thực hiện các thực nghiệm và kết quả đạt được.
Sau cùng, kết quả nhận được cho chúng ta cái nhìn tương đối về sự khác biệt giữa bốn thuật toán được lựa chọn. - Thiết lập thực nghiệm: Lựa chọn hai topology mạng là FUNET và BSO, mô phỏng bằng Mininet và sử dụng các công cụ như Netresec, Wireshark, vv để tạo ra các traffic flow trong mạng, truyền gói tin trong mạng hoặc để thay đổi các gia tri Loss, Delay theo thời gian. Sau cùng, Ryu confroller được lựa chọn như một SDN controller để có thể triển khai các thuật toán MAB. - Kết quả thực nghiệm: Mỗi thuật toán được chạy riêng trong 12 giờ đối với mỗi topology mạng, trong hai kịch bản là Underload và Overload.
Kết quả là các thuật toán cho ra hiệu suất gần giống nhau trong kịch bản Underload nhưng hai thuật toán UCB cho hiệu suất tốt hơn hẳn thuật toán e-greedy, Softmax trong kịch bản Overload. - Đánh giá thực nghiệm: Thực nghiệm thành công trong việc chạy bốn thuật toán và đưa ra những đánh giá so sánh bằng con số cụ thể. Qua đó có thể thấy việc lựa chọn các thuật toán UCB là một lựa chọn tiềm năng cho bải toán lựa chọn nút đầu ra tối ưu trong một mạng SDN phân tán. Chương 5 Kết luận và hướng phát triển Về cơ bản, luận văn và thực nghiệm đã đạt được mục tiêu đề ra, đó là đề xuất một cách tiếp cận mới để chọn ra một nút đầu ra tối ưu trong một mạng SDN dựa trên các thuật toán học tăng cường.
Thực nghiệm rút ra kết luận rằng, các thuật toán UCB có hiệu suất hơn hẳn các thuật toán được chọn khác, đặc biệt trong điều kiện mạng overload. Tuy nhiên, giá trị quyết định tới “Phần thưởng” trong mỗi lần chọn nút đầu ra là QoS được mô tả một cách đơn giản — là một hàm tuyến tính giữa Delay và Loss — chưa thể hiện được độ phức tạp trong môi trường mạng thực tế. Đây là một cánh cửa mở để tác giả luận văn tiếp tục nghiên cứu và đưa ra phương pháp đánh giá “Phần thưởng” sao cho có thé tiệm cận với các giá trị trong một mạng thực tế. Tài liệu tham khảo CHUONG 2.1 Lựa chọn nút biên và định tuyến nội miền Kiến trúc định tuyến hai tầng của Internet được thiết kế để có sự tách biệt rõ ràng giữa các giao thức định tuyến nội miền và liên miền.
Ví dụ, giao thức định tuyến liên miền cho phép các bộ định tuyến biên học cách tiếp cận các đích bên ngoài, trong khi giao thức nội miền xác định cách điều hướng lưu lượng từ một bộ định tuyến trong Hệ thống tu tri (Autonomous System - AS) sang một bộ định tuyến khác. Tuy nhiên, vai trò thích hợp của hai giao thức trở nên không rõ ràng khi AS học các tuyến đến đích tại nhiều bộ định tuyến biên. Đây là tình huống phát sinh khá thường xuyên trong các cơ chế định tuyến hiện nay. Vì các nhà cung cấp dịch vụ ngang hàng tại nhiều địa điểm, nên về cơ bản, tất cả lưu lượng truy cập từ khách hàng tới mạng Internet đều có thể lựa chọn nhiều bộ định tuyến biên.
Ngoài ra, nhiều khách hàng kết nối với nhà cung cấp của họ ở nhiều địa điểm để có khả năng chịu lỗi và cân bằng tải linh hoạt hơn, dẫn đến cũng có nhiều bộ định tuyến đầu ra cho những điểm đến này. Có thê cho rằng việc lựa chọn trong số nhiều điểm đầu ra hiện là một phần cơ bản của kiến trúc định tuyến Internet, không phụ thuộc vào bộ giao thức định tuyến hiện tại. Trong Internet ngày nay, các bộ định tuyến biên học các tuyến đến các destination prefix thông qua giao thức Border Gateway Protocol (BGP). Khi nhiều bộ định tuyến biên có các tuyến đường “tốt như nhau” theo nghĩa BGP (ví dụ, tùy chọn cục bộ, độ dài đường dẫn AS, v.), mỗi bộ định tuyến trong AS sẽ hướng lưu lượng đến bộ định tuyến biên gần nhất, theo giao thức Interior Gateway Protocol (IGP).
Chính sách định tuyến Early-Exit hoặc Hot-Potato được hard-code trong quy trình quyết định BGP được triển khai trên mỗi bộ định tuyến. Định tuyến Hot-Potato là một cơ chế hiệu quả vì hai lý do chính. Đầu tiên, định tuyến Hot-Potato có thể hạn chế mức tiêu thụ tài nguyên băng thông trong mạng bằng cách chuyên lưu lượng đến AS tiếp theo càng sớm càng tốt. Thứ hai, theo định tuyến Hot-Potato, lựa chọn điểm ra của bộ định tuyến được đảm bảo nhất quán với các bộ định tuyến khác dọc theo đường chuyên tiếp, bởi vì các gói 8 được chuyên tiếp đến các bộ định tuyến lân cận đã chọn tuyến BGP có cùng điểm ra (gần nhất).
Mặc dù chuyển tiếp nhất quán rõ ràng là một thuộc tính quan trọng đối với bất kỳ hệ thống định tuyến nào, nhưng các bộ định tuyến hiện có những cách khác để đạt được mục tiêu này. Đặc biệt, tính khả dụng cao hơn của công nghệ đường ham (tunnel) cho phép các quy tắc lựa chọn lối ra tỉnh vi hơn, không bị ràng buộc với các số liệu IGP. Các nhà cung cấp dịch vụ Internet (ISP) ngày càng sử dụng nhiều công nghệ tạo tunnel - chẳng hạn như đóng gói IP-in-IP hoặc Chuyển mạch nhãn đa giao thức (Multi-Protocol Label Switching - MPLS) - để hỗ trợ mạng riêng ảo (Virtual Private Network - VPN) hoặc để tránh chạy BGP trên các bộ định tuyến nội bộ của họ. Nhìn chung, cơ chế định tuyến Hot-Potato có những nhược điểm sau: ¢ Qua han ché: Co ché co ban dua ra một chính sách cụ thé thay vì hỗ tro cdc muc tiéu hiéu suat da dang quan trong đối với nhân viên quản trị mạng.
e_ Dễ gây gián đoạn: Những thay đổi nhỏ về khoảng cách IGP đôi khi có thê dẫn đến những thay đổi lớn về lưu lượng, độ trễ hội tụ kéo dài và cập nhật BGP cho các miền lân cận. se _ Quá phức tạp: Các nhân viên quản trị mạng buộc phải đánh giá tác động của những thay đổi trong chỉ số IGP đối với các quyết định định tuyến BGP, thay vì xem hai phần của hệ thống định tuyến một cách riêng biệt. Chọn nút đầu ra và tính toán đường dẫn chuyên tiếp đến nút đầu ra là hai chức năng rất khác biệt và tôi tin rằng chúng nên được tách rời. Các tuyến đường bên trong mạng nên được chọn dựa trên một số mục tiêu hiệu suất có ý nghĩa, trong khi lựa chọn nút đầu ra phải linh hoạt để hỗ trợ một tập hợp rộng hơn các mục tiêu kỹ thuật lưu lượng.
Các mục tiêu này khác nhau tùy theo mạng và destination prefix, do đó, một cơ chế áp đặt một chính sách lựa chọn nút đầu ra duy nhất không thể đáp ứng các yêu cầu đa dạng này. Phần này tiếp tục trình bày về một số giải pháp lựa chọn nút đầu ra liên quan.2 Các giải pháp liên quan 2.