Luận văn Thạc sĩ Hệ thống thông tin: Điều khiển tắc nghẽn mạng internet bằng deep reinforcement learning

Chia sẻ: Matroinho | Ngày: | Loại File: PDF | Số trang:53

Thêm vào BST

Báo xấu

21
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn "Điều khiển tắc nghẽn mạng internet bằng deep reinforcement learning" được chia làm các phần sau: Chương 1 sẽ nói khái quát về cấu trúc mạng internet; điều khiển tắc nghẽn và các các cơ chế điều khiển tắc nghẽn; học tăng cường và học tăng cường sâu; Chương 2 sẽ giới thiệu các nghiên cứu liên quan về 2 hướng tiếp cận rule-based và ML-based. Chương 3 sẽ đề xuất giải pháp và đánh giá hiệu năng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Hệ thống thông tin: Điều khiển tắc nghẽn mạng internet bằng deep reinforcement learning

UBND TỈNH BÌNH DƯƠNG TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT LÊ HUY TÊN ĐỀ TÀI ĐIỀU KHIỂN TẮC NGHẼN MẠNG INTERNET BẰNG DEEP REINFORCEMENT LEARNING CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN MÃ SỐ: 8480104 LUẬN VĂN THẠC SỸ BÌNH DƯƠNG, năm 2020
UBND TỈNH BÌNH DƯƠNG TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT LÊ HUY TÊN ĐỀ TÀI ĐIỀU KHIỂN TẮC NGHẼN MẠNG INTERNET BẰNG DEEP REINFORCEMENT LEARNING. CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN MÃ SỐ: 8480104 LUẬN VĂN THẠC SỸ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. LÊ TUẤN ANH BÌNH DƯƠNG, năm 2020
LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong Luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này đã được cảm ơn và các thông tin trích dẫn trong Luận văn đã được chỉ rõ nguồn gốc. Học viên thực hiện đề tài i
LỜI CẢM ƠN Để hoàn thành được bài luận văn thạc sĩ này, tôi xin bày tỏ sự cảm kích đặc biệt tới thầy hướng dẫn khoa học của tôi, Phó Giáo sư Tiến sĩ Lê Tuấn Anh - Người đã định hướng, trực tiếp dẫn dắt và cố vấn cho tôi trong suốt thời gian thực hiện luận văn. Xin chân thành cảm ơn những bài giảng và bài báo khoa học của thầy giới thiệu đã giúp cho tôi mở mang thêm nhiều kiến thức hữu ích về điều khiển tắc nghẽn mạng internet. Đồng thời, thầy cũng là người luôn cho tôi những lời khuyên vô cùng quý giá về cả kiến thức chuyên môn cũng như định hướng phát triển sự nghiệp. Một lần nữa, tôi xin gửi lời cảm ơn đến thầy bằng tất cả tấm lòng và sự biết ơn của mình. Tôi cũng xin gửi lời cảm ơn chân thành đến Viện Đào tạo Sau Đại học, trường đại học Thủ Dầu Một, đã giảng dạy và đã hỗ trợ tôi trong suốt quá trình học và quá trình làm luận văn thạc sĩ này. Sau cùng, tôi xin tỏ lòng biết ơn đến cha mẹ, người thân và bạn bè đã luôn bên cạnh ủng hộ, động viên tôi trong cuộc sống cũng như trong thời gian hoàn thành luận văn thạc sĩ. Học viên thực hiện đề tài ii
MỤC LỤC LỜI CAM ĐOAN .............................................................................................................. i LỜI CẢM ƠN ................................................................................................................... ii MỤC LỤC ....................................................................................................................... iii DANH MỤC BẢNG ....................................................................................................... iv DANH MỤC HÌNH, ĐỒ THỊ .......................................................................................... v DANH MỤC CHỮ VIẾT TẮT ....................................................................................... vi MỞ ĐẦU .......................................................................................................................... 1 Chương 1. TỔNG QUAN ................................................................................................. 3 1.1 Giao thức TCP/IP .................................................................................... 3 1.2 TCP và cơ chế điều khiển tắc nghẽn ....................................................... 5 1.2.1 Quá trình slow-start và congestion avoidance .............................................. 5 1.2.2 Quá trình Fast-Retransmit............................................................................. 5 1.2.3 Quá trình Fast-Recovery ............................................................................... 5 1.3 Học tăng cường ....................................................................................... 6 1.3.1 Các khái niệm cơ bản.................................................................................... 6 1.3.2 Quy trình quyết định Markov (Markov Decision Process – MDP) .............. 7 1.3.3 Q – Learning ................................................................................................. 8 1.3.4 Học tăng cường sâu (Deep Q – Learning) .................................................... 9 Chương 2. CÁC NGHIÊN CỨU LIÊN QUAN.............................................................. 11 2.1 Kỹ thuật điều khiển tắc nghẽn dựa vào rule-based ............................... 11 2.1.1 TCP Tahoe .................................................................................................. 11 2.1.2 TCP Reno.................................................................................................... 11 2.1.3 TCP New Reno ........................................................................................... 12 2.1.4 TCP Cubic .................................................................................................. 13 2.2 Kỹ thuật điều khiển tắc nghẽn dựa vào ML .......................................... 14 2.3 DRL - PCC Aurora ............................................................................... 15 Chương 3. ĐỀ XUẤT GIẢI PHÁP ................................................................................ 17 3.1 Đề xuất cải tiến...................................................................................... 17 3.2 Xây dựng mô hình ................................................................................. 21 2.4 Đánh giá mô hình đề xuất ..................................................................... 23 3.3.1 Đánh giá huấn luyện ................................................................................... 23 3.3.2 Đánh giá sự thích ứng và độ ổn định .......................................................... 24 2.5 Cài đặt thực nghiệm (Testbed) và kết quả ............................................ 25 2.6 Đánh giá kết quả thực nghiệm .............................................................. 27 KẾT LUẬN .................................................................................................................... 28 Tài Liệu Tham Khảo ....................................................................................................... 29 iii
DANH MỤC BẢNG iv
DANH MỤC HÌNH, ĐỒ THỊ Hình 1 Mô hình TCP / IP ....................................................................................... 3 Hình 2 Mô hình học tăng cường ............................................................................ 6 Hình 3 Quy trình quyết định Markov..................................................................... 8 Hình 4 Mô hình Deep Q Learning ......................................................................... 9 Hình 5 So sánh thông lượng giữa TCP CUBIC và Aurora .................................. 16 Hình 6 So sánh thông lượng giữa 2 phương pháp TCP CUBIC và Aurora, thông lượng được điều chỉnh sau mỗi 5 giây từ 20Mbps đến 40Mbps và ngược lại. .... 16 Hình 7 Mô hình huấn luyện PCC Aurora Loss .................................................... 19 Hình 8 Mô hình điều khiển PCC Aurora Loss ..................................................... 21 Hình 9 Giá trị hàm reward với các giá trị k khác nhau ........................................ 22 Hình 10 Giá trị hàm reward với các giá trị k khác nhau ...................................... 23 Hình 11 Kết quả hàm reward khi huấn luyện Aurora Loss ................................ 23 Hình 12 Kết quả hàm reward khi huấn luyện Aurora ......................................... 24 Hình 13 So sánh thông lượng giữa TCP CUBIC, Aurora, Aurora Loss với giả lập tỉ lệ mất gói là 3-5% ............................................................................................. 24 Hình 14 Độ đáp ứng của các giao thức khi môi trường mạng thay đổi sau mỗi 5 giây ....................................................................................................................... 25 Hình 15 Mô hình thực nghiệm trên mạng internet............................................... 25 Hình 16 Thông lượng của PCC Aurora ............................................................... 26 Hình 17 Thông lượng của PCC Aurora loss ........................................................ 27 v
DANH MỤC CHỮ VIẾT TẮT TCP : Transmission Control Protocol IP : Internet Protocol RL : Reinforcement Learning DRL : Deep Reinforcement Learning ML: Machine learning NN: Neural Network FFNN : Feed Forwarding Neural Network PCC : Performance Oriented Congestion Control Cwnd : Congestion Window vi
MỞ ĐẦU Sự tăng trưởng chưa từng có của lưu lượng truy cập mạng, đặc biệt là lưu lượng truy cập mạng di động, đã ảnh hưởng rất lớn tới mạng Internet ngày nay. Mặc dù năng lực của các liên kết có dây và không dây đã liên tục tăng lên nhưng khoảng cách giữa nhu cầu của người dùng và những gì mạng Internet có thể cung cấp được cũng đang lớn dần lên. Hơn nữa, nhiều ứng dụng mới nổi không chỉ đòi hỏi thông lượng và độ tin cậy cao, mà còn cần độ trễ thấp, nói cách khác là đòi hỏi trải nghiệm người dùng cao (Quality of Experience – QoE). Mặc dù cách tiếp cận mạnh mẽ của việc triển khai các liên kết có dây và không dây với công suất cao hơn giúp giảm một phần nào đó của vấn đề, tuy nhiên một cách tiếp cận khả thi hơn là xem xét lại thiết kế lớp giao thức cao hơn, để sử dụng hiệu quả hơn khả năng liên kết lớp vật lý. Điều khiển tắc nghẽn là chức năng kết nối mạng quan trọng nhất của lớp vận chuyển, đảm bảo phân phối dữ liệu ứng dụng đáng tin cậy. Tuy nhiên, việc thiết kế một giao thức điều khiển tắc nghẽn rất khó khăn. Đầu tiên, mạng lưới giao vận hiện tại là một mạng lưới các hàng đợi cực kỳ phức tạp và quy mô lớn. Bản thân các máy chủ đầu cuối TCP bao gồm các hàng đợi được kết nối với nhau trong kernel. Khi luồng TCP xâm nhập vào Internet, nó đi qua các hàng đợi khác nhau tại các bộ định tuyến/chuyển mạch dọc theo đường dẫn từ đầu cuối đến đầu cuối, mỗi luồng được chia sẻ chung lưu lượng với các giao thức khác nhau (ví dụ: TCP và UDP) và được vận hành theo một số quy tắc lập lịch nhất định. Để có thể hiểu được một mạng lưới phức tạp như vậy, và phát triển một giao thức điều khiển tắc nghẽn hiệu quả, ta sẽ cần một nguồn lực rất lớn. Thứ hai, nếu tuân theo nguyên tắc của các đầu cuối, các tác nhân tại các máy chủ đầu cuối phải thăm dò trạng thái mạng và đưa ra quyết định độc lập mà không cần phối hợp với nhau. Trạng thái mạng thu thập được thường dễ bị lỗi và bị trễ, và tác động của một quyết định cũng sẽ bị trễ và phụ thuộc vào hành động của các máy chủ cạnh tranh khác, lúc này các quyết định đó dường như không còn nhiều ý nghĩa. Thứ ba, nếu nói đến các bộ định tuyến, thuật toán phải cực kỳ đơn giản (ví dụ: stateless) để đảm bảo khả năng mở rộng, vì bộ định tuyến thường phải xử lý một lưu lượng cực kỳ lớn. Cuối cùng, 1
khi nhiều thiết bị không dây kết nối vào hệ thống, các liên kết không dây với sự đa dạng về độ tiêu hao và băng thông cũng đặt ra nhiều thách thức lớn đối với thiết kế điều khiển tắc nghẽn. Nhiều giao thức điều khiển tắc nghẽn hiệu quả cũng đã được phát triển trong ba thập kỷ qua. Tuy nhiên, nhiều đề án hiện có đều chỉ dựa trên một số giả định cơ bản. Ví dụ về các thuật toán điều khiển tắc nghẽn hiện nay phần nào đó không còn phù hợp là về độ mất gói ngẫu nhiên trong một đường truyền băng thông lớn. Với các thuật toán điều khiển tắc nghẽn hiện nay, nếu phát hiện một gói tin bị mất, thì thuật toán liền giảm đi 1/2 tốc độ truyền, dẫn tới băng thông cũng bị lãng phí đi 1/2 trong khi sự mất gói này không nói lên tình trạng mạng là đang tắc nghẽn, mà chỉ là một sự kiện mất gói rất nhỏ. Để có thể giải quyết được vấn đề này, chúng ta cần phải thiết kế một thuật toán có thể nhận biết được đâu là tắc nghẽn thật sự và đâu chỉ là một sự mất gói ngẫu nhiên không liền mạch. Với sự phát triển mạnh mẽ của học máy và học sâu hiện nay, nhiều lĩnh vực trong cuộc sống đã và đang được cải tiến thành công. Học máy và học sâu dựa nhiều vào dữ liệu đã thu thập trong quá khứ, và có thể giải quyết nhiều bài toán phức tạp với nhiều biến số. Vì vậy để tránh sử dụng các giả định có sẵn và có phần không còn đúng với mật độ, sự phức tạp của mạng internet hiện tại, nghiên cứu này sẽ áp dụng kết hợp học máy và học sâu để phát triển giao thức điều khiển tắc nghẽn. Dựa vào các dữ liệu đã có của hệ thống mạng, học máy và học sâu có thể rút trích ra được những tính chất quan trọng trong việc điều khiển tắc nghẽn mạng internet. Cụ thể trong luận văn này, tôi chú trọng nghiên cứu một phương pháp học máy có thể đáp ứng được với môi trường thay đổi ngẫu nhiên đó là phương pháp học tăng cường sâu (Deep Reinforcement Learning – DRL) để áp dụng vào điều khiển tắc nghẽn mạng internet. Luận văn này được chia làm các phần sau: Chương 1 sẽ nói khái quát về cấu trúc mạng internet; điều khiển tắc nghẽn và các các cơ chế điều khiển tắc nghẽn; học tăng cường và học tăng cường sâu; Chương 2 sẽ giới thiệu các nghiên cứu liên quan về 2 hướng tiếp cận rule-based và ML-based. Chương 3 sẽ đề xuất giải pháp và đánh giá hiệu năng. 2
Chương 1. TỔNG QUAN 1.1 Giao thức TCP/IP TCP/ IP (Transmission Control Protocol/ Internet Protocol - Giao thức điều khiển truyền nhận/ Giao thức liên mạng), là một bộ giao thức trao đổi thông tin được sử dụng để truyền tải và kết nối các thiết bị trong mạng Internet. TCP/IP được phát triển để mạng được tin cậy hơn, cùng với khả năng phục hồi tự động. Hình 1 Mô hình TCP / IP Cách thức hoạt động của mô hình TCP/IP Phân tích từ tên gọi, TCP/IP là sự kết hợp giữa 2 giao thức đó là giao thức TCP và giao thức IP. Trong đó giao thức IP (Internet Protocol - Giao thức liên mạng) cho phép các gói tin được gửi từ máy nguồn đến máy đích đã định sẵn, bằng cách thêm các thông tin dẫn đường vào các gói tin để các gói tin được đến đúng đích đã định sẵn ban đầu. Và giao thức TCP (Transmission Control Protocol - Giao thức truyền vận) đóng vai trò kiểm tra và đảm bảo sự an toàn cho mỗi gói tin trong quá trình di chuyển qua các trạm trung gian rồi đến trạm đích. Trong quá trình này, nếu giao thức TCP nhận thấy gói tin bị lỗi, một tín hiệu sẽ được truyền ngược lại và yêu cầu hệ thống gửi lại một gói tin khác. Quá trình hoạt động này sẽ được làm rõ hơn ở chức năng của mỗi tầng trong mô hình TCP/IP. Chức năng của các tầng trong mô hình TCP/IP Một mô hình TCP/IP tiêu chuẩn bao gồm 4 lớp được chồng lên nhau, bắt đầu từ tầng thấp nhất là Tầng vật lý (Physical) → Tầng mạng (Network) → Tầng giao vận (Transport) và cuối cùng là Tầng ứng dụng (Application). 3
Tầng 4 - Tầng Ứng dụng (Application) Đây là lớp giao tiếp trên cùng của mô hình. Đúng với tên gọi, tầng Ứng dụng đảm nhận vai trò giao tiếp dữ liệu giữa 2 máy khác nhau thông qua các dịch vụ mạng khác nhau (duyệt web, chat, gửi email, một số giao thức trao đổi dữ liệu: SMTP, SSH, FTP,...). Dữ liệu khi đến đây sẽ được định dạng theo kiểu Byte nối Byte, cùng với đó là các thông tin định tuyến giúp xác định đường đi đúng của một gói tin. Tầng 3 - Tầng Giao vận (Transport) Chức năng chính của tầng 3 là xử lý vấn đề giao tiếp giữa các máy chủ trong cùng một mạng hoặc khác mạng được kết nối với nhau thông qua bộ định tuyến. Tại đây dữ liệu sẽ được phân đoạn, mỗi đoạn sẽ không bằng nhau nhưng kích thước phải nhỏ hơn 64KB. Cấu trúc đầy đủ của một Segment lúc này là Header chứa thông tin điều khiển và sau đó là dữ liệu. Trong tầng này còn bao gồm 2 giao thức cốt lõi là TCP và UDP. Trong đó, TCP đảm bảo chất lượng gói tin nhưng tiêu tốn thời gian khá lâu để kiểm tra đầy đủ thông tin từ thứ tự dữ liệu cho đến việc kiểm soát vấn đề tắc nghẽn lưu lượng dữ liệu. Trái với điều đó, UDP cho thấy tốc độ truyền tải nhanh hơn nhưng lại không đảm bảo được chất lượng dữ liệu được gửi đi. Tầng 2 - Tầng mạng (Internet) Gần giống như tầng mạng của mô hình OSI. Tại đây, nó cũng được định nghĩa là một giao thức chịu trách nhiệm truyền tải dữ liệu một cách logic trong mạng. Các phân đoạn dữ liệu sẽ được đóng gói (Packets) với kích thước mỗi gói phù hợp với mạng chuyển mạch mà nó dùng để truyền dữ liệu. Lúc này, các gói tin được chèn thêm phần Header chứa thông tin của tầng mạng và tiếp tục được chuyển đến tầng tiếp theo. Các giao thức chính trong tầng là IP, ICMP và ARP. Tầng 1 - Tầng Vật lý (Physical) Là sự kết hợp giữa tầng Vật lý và tầng liên kết dữ liệu của mô hình OSI. Chịu trách nhiệm truyền dữ liệu giữa hai thiết bị trong cùng một mạng. Tại đây, các gói dữ liệu được đóng vào khung (gọi là Frame) và được định tuyến đi đến đích đã được chỉ định ban đầu. 4
1.2 TCP và cơ chế điều khiển tắc nghẽn 1.2.1 Quá trình slow-start và congestion avoidance Trong quá trình slow-start, khi mà kết nối vừa được thiết lập, cwnd được thiết lập giá trị là 1 MSS (Maximum segment size). Sau mỗi gói “ACK mới” nhận được, cwnd được tăng tuyến tính lên 1 đơn vị. Việc tăng tuyến tính này được tiếp tục cho tới khi có gói bị mất hoặc đạt ngưỡng ssthresh. Trong trường hợp có gói bị mất, ssthresh = cwnd/2 và cwnd được trả về bằng 1. Trong trường hợp cwnd đạt ngưỡng ssthresh, thực thể gửi TCP chuyển sang quá trình congestion avoidance. Khi này, thay vì tăng theo hàm mũ cơ số 2, cwnd tăng tuyến tính: cwnd = cwnd + 1/cwnd. Việc tăng này sẽ tiếp tục cho đến khi có gói bị mất. Quá trình slow-start nhằm mục đích “thăm dò” khả năng của đường truyền hiện tại. Mặc dù được thiết lập ở mức thấp (cwnd =1), song lại tăng rất nhanh tương tự như quá trình hiệu chỉnh thô khả năng phát gói. Khi xảy ra tắc nghẽn, quá trình congestion avoidance lại giống như quá trình hiệu chỉnh tinh, đồng thời, cũng là để hạn chế tắc nghẽn. Mục đích cuối cùng của cả hai quá trình là đảm bảo việc phát gói ở mức cao nhất có thể được. 1.2.2 Quá trình Fast-Retransmit Mục đích của Fast-Retransmit là tăng tốc quá trình truyền lại bằng cách cho phép đầu gửi truyền lại gói bị mất càng sớm càng tốt ngay khi có đủ căn cứ về việc mất gói. Có nghĩa là thay vì phải chờ đến khi time-out, đầu phát có thể truyền lại ngay khi cần thiết, đó là khi nhận được liên tiếp 3 biên nhận lặp (dupAcks). 1.2.3 Quá trình Fast-Recovery Với TCP Tahoe, kết nối luôn trở về quá trình slow-start ngay khi phát hiện mất gói. Tuy nhiên, nếu như window size lớn và tỉ lệ mất gói là ít khi xảy ra, thì việc đó là không cần thiết vì hoàn toàn có thể chuyển sang trạng thái congestion avoidance. Mục đích của Fast-Recovery nhằm thực hiện ý tưởng trên. Trong quá trình Fast-Retransmit, bên gửi ghi nhận lại gói truyền lại. Sau khi gói đã truyền lại, giá trị của ssthresh và cwnd sẽ được hiệu chỉnh theo nguyên tắc: 5
𝑠𝑠𝑡ℎ𝑟𝑒𝑠𝑠 = 𝑐𝑤𝑛𝑑/2 ! 𝑐𝑤𝑛𝑑 = 𝑠𝑠ℎ𝑟𝑒𝑠𝑠 Điều này đồng nghĩa với kết nối sẽ tiếp tục với quá trình congestion avoidance, với giá trị cửa sổ phát cwnd giảm xuống còn bằng một nửa chứ không phải xuống bằng. 1.3 Học tăng cường Học tăng cường (Reinforcement Learning – RL) là một trong ba kiểu học máy chính bên cạnh học giám sát (Supervised Learning) và học không giám sát (Unsupervised Learning). Bản chất của RL là trial-and-error, nghĩa là thử đi thử lại và rút ra kinh nghiệm sau mỗi lần thử như vậy. 1.3.1 Các khái niệm cơ bản Gồm 7 khái niệm chính: Agent, Environment, State, Action, Reward, Episode, Policy. Agent là tác nhân, chịu trách nhiệm thực hiện tương tác với Môi trường (Environment) bằng các hành động (Action). Sau mỗi hành động, môi trường trả về cho tác nhân một trạng thái (State) và phần thưởng (Reward) tương ứng với trạng thái đó. Khi agent đạt được trạng thái kết thúc thì quá trình kết thúc. Một loạt các tương tác giữa agent và environment từ thời điểm bắt đầu đến lúc kết thúc này được gọi là một Episode. Trong một episode, agent sẽ cố gắng chọn ra các actions tối ưu để tối đa hóa reward nhận được sau mỗi episode. Cách mà agent chọn những actions đó là Policy. Có thể thấy policy cũng có policy này và policy kia; mục đích của RL là tìm ra policy tốt nhất. Hình dưới đây mô tả tương tác giữa Agent - Environment: State Reward Policy Action Hình 2 Mô hình học tăng cường 6
1.3.2 Quy trình quyết định Markov (Markov Decision Process – MDP) Quy trình quyết định Markov (MDP) cung cấp một nền tảng toán học cho việc mô hình hóa việc ra quyết định trong các tình huống mà kết quả là một phần ngẫu nhiên và một phần dưới sự điều khiển của một người ra quyết định. MDP rất hữu dụng cho việc học một loạt bài toán tối ưu hóa được giải quyết thông qua quy hoạch động và học tăng cường. MDP được biết đến sớm nhất là vào những năm 1950 (cf. Bellman 1957). Một cốt lõi của nghiên cứu về quá trình ra quyết định Markov là từ kết quả của cuốn sách của Ronald A. Howard[7] xuất bản năm 1960, Quy hoạch động và quá trình Markov. Chúng được sử dụng trong rất nhiều các lĩnh vực khác nhau, bao gồm robot, điều khiển tự động, kinh tế, và chế tạo. Chính xác hơn, một quá trình quyết định Markov là một quá trình điều khiển ngẫu nhiên thời gian rời rạc. Tại mỗi bước thời gian, quá trình này trong một vài trạng thái s, và người ra quyết định có thể chọn bất kỳ hành động a nào có hiệu lực trong trạng thái s. Quá trình này đáp ứng tại bước thời gian tiếp theo bằng cách di chuyển ngẫu nhiên vào một trạng thái mới s’ và đưa ra cho người ra quyết định một phần thưởng tương ứng Ra(s,s’) Xác suất mà quá trình di chuyển vào trạng thái mới của nó s’ bị ảnh hưởng bởi hành động được chọn. Đặc biệt, nó được đưa ra bởi hàm chuyển tiếp trạng thái Pa(s,s’). Do đó, trạng thái kế tiếp s’ phụ thuộc vào trạng thái hiện tại s và hành động của người ra quyết định a. Nhưng s và a đã cho, lại độc lập có điều kiện với toàn bộ trạng thái và hành động trước đó; nói cách khác, các trạng thái chuyển tiếp của một quá trình MDP thỏa mãn thuộc tính Markov. Quá trình quyết định Markov là một phần mở rộng của chuỗi Markov; khác biệt là ở sự bổ sung của các hành động (cho phép lựa chọn) và phần thưởng (cho động cơ). Ngược lại, nếu chỉ có một hành động tồn tại cho mỗi trạng thái và tất cả các phần thưởng là giống nhau (ví dụ: zero), một quá trình quyết định Markov làm giảm một chuỗi Markov. 7
Một MDP là một bộ 5 biến (S, A, T, R, γ): • S là không gian trạng thái, • A không gian hành động, • T: S × A × S → [0, 1] là hàm chuyển dịch (tập các xác suất chuyển dịch giữa các trạng thái), • R: S × A × S → R là hàm thưởng, R là một tập liên tiếp các phần thưởng có thể trong khoảng Rmax ∈ R+ (e.g., [0, Rmax]), • γ ∈ [0, 1) là nhân tố giảm trừ, Hình 3 Quy trình quyết định Markov[8] 1.3.3 Q – Learning Làm thế nào mà agent biết phải chọn action nào để đạt được reward lớn nhất? Câu trả lời là sử dụng một giá trị gọi là Q-value được tính bằng công thức: 𝑄(𝑠, 𝑎) = 𝑟(𝑠, 𝑎) + 𝛾 max 𝑄(𝑠 " , 𝑎) ! Trong đó Q(s, a) là Q-value khi thực hiện action a tại state s; r(s, a) là reward nhận được; s' là state kế tiếp. γ là hệ số discount, đảm bảo càng "xa" đích Q-value càng nhỏ Công thức này cho thấy Q-value của action a tại state s bằng reward r(s,a) cộng với Q-value lớn nhất của các states s' tiếp theo khi thực hiện các action a. Vậy đó, chỉ với công thức đơn giản kia chúng ta có thể tạo ra một ma trận state- action như một lookup table. Từ đó với mỗi state agent chỉ cần tìm action nào có Q-value lớn nhất là xong. Tuy nhiên, như mình đã nói ở trên thì RL là một 8
stochastic process nên Q-value ở thời điểm trước và sau khi thực hiện action sẽ khác nhau. Khác biệt này gọi là Temporal Difference: 𝑇𝐷 (𝑎, 𝑠) = 𝑅(𝑠, 𝑎 ) + 𝛾 max 𝑄(𝑠 " , 𝑎" ) − 𝑄#$% (𝑠, 𝑎) !" Như vậy, ma trận Q(s, a) cần phải cập nhật trọng số dựa trên TD: 𝑄# (𝑠, 𝑎 ) = 𝑄#$% (𝑠, 𝑎 ) + 𝛼𝑇𝐷# (𝑎, 𝑠) Trong đó α là learning rate. Qua các lần agent thực hiện actions, Q(s, a) sẽ dần hội tụ. Quá trình này chính là Q – Learning. 1.3.4 Học tăng cường sâu (Deep Q – Learning) Mục đích của chúng ta là chọn ra action thích hợp cho một state nào đó; hay nói cách khác, chúng ta state làm input, output là một action/ Để giải quyết việc này ta có thể sử dụng một Neural Network (NN). Những gì cần làm chỉ là bỏ đi lookup table Q(s,a) và thay thế bằng một NN đơn giản. State Q - Value Action Q Learning Q – Value Action 1 Q – Value Action 2 State Q – Value Action 3 Q – Value Action 4 Hình 4 Mô hình Deep Q Learning Tuy nhiên, vẫn còn thiếu phần quan trọng nhất của NN. Đó chính là hàm Loss. Mục đích của ta là bắt NN học được cách ước lượng Q-Value cho các actions 9
một cách chính xác nên đương nhiên hàm Loss phải tính được sai số giữa Q-value thực tế và dự đoán. Nó chính là TD2(a,s). Viết dưới dạng đầy đủ: 𝐿𝑜𝑠𝑠 = (𝑟 + 𝛾𝑚𝑎𝑥!! 𝑄 (𝑠 " , 𝑎" ; 𝜃 " ) − 𝑄(𝑠, 𝑎; 𝜃 ))# Tóm lại, Deep Q-Learning thực hiện các bước sau: 1. Enviroment đưa vào mạng một state s; đầu ra là các Q-value của các action tương ứng. 2. Agent chọn action bằng một Policy và thực hiện action đó. 3. Environment trả lại state s' và reward r là kết quả của action a và lưu experience tuple [s, a, r, s'] vào memory 4. Thực hiện sample các experience thành một vài batches và tiến hành train NN 5. Lặp lại đến khi kết thúc M episodes 10
Chương 2. CÁC NGHIÊN CỨU LIÊN QUAN Các thiết kế thuật toán điều khiển tắc nghẽn có thể chia làm hai tiếp cập: phương pháp rule-based và phương pháp ML-based. 2.1 Kỹ thuật điều khiển tắc nghẽn dựa vào rule-based Thông thường, điều khiển tắc nghẽn thuật toán theo rule-based được xác định dựa trên bài toán tối ưu cho mô hình mạng cụ thể. Hiệu năng và độ ổn định của hệ thống dễ dàng kiểm chứng; thuật toán điều khiển là phân tán và đơn giản trong tính toán. Sau đây là một số giao thức tiêu biểu theo hướng tiếp cận rule-based. 2.1.1 TCP Tahoe Đặc trưng Tahoe tăng congestion window (cwnd) theo hàm mũ trong giai đoạn Slow Start và tăng tuyến tính trong giai đoạn congestion avoidance. Tahoe dùng một timer canh giờ để xét xem liệu một gói tin có “timeout” hay chưa. Trong giai đoạn congestion advoidance, khi phát hiện tắc nghẽn (một gói tin bị time out) thì threshold sẽ bị giảm còn bằng ½ của cwnd lúc đó. Đồng thời cwnd sẽ bị giảm xuống còn 1 và bắt đầu lại từ giai đoạn slow start. Khuyết điểm Chính vì sử dụng timer để xét một gói tin bị timeout, nên vấn đề chính ở TCP Tahoe là thời gian chờ timeout để phát hiện gói tin bị mất là khá lâu. Các gói tin ACK không được gởi ngay sau mỗi gói tin mà được gởi cộng dồn. Vì TCP Tahoe sử dụng phương thức “go back N” nên mỗi khi có một gói tin bị mất thì đường truyền sẽ trống trong một khoảng thời gian. Gây lãng phí tài nguyên. Không sử dụng tối ưu băng thông. 2.1.2 TCP Reno Tương tự như TCP Tahoe ở giai đoạn slow start nhưng có một số cải tiến. Giúp phát hiện gói tin bị mất sớm hơn trước khi một gói tin bị timeout. Tăng hiệu suất gởi nhận. 11
Điểm khác biệt Với mỗi gói tin được gởi thì các gói ACK trả về sẽ được trả ngay lập tức theo đúng thứ tự của gói tin đã nhận, chứ không cộng dồn các gói ACK như TCP Tahoe. TCP Reno có cài đặt thêm thuật toán “Fast-Retransmit” khi gặp trường hợp có 3 gói ACK bị lặp lại. Reno sẽ giảm đặt giá trị của cwnd mới bằng ½ giá trị của cwnd hiện tại. Và đạt ngưỡng threshold mới bằng giá trị của cwnd mới. Đồng thời chuyển nhanh lại gói tin đã bị mất (Fast-Retransmit) và bước vào một pha gọi là Fast Recovery. Nếu sau pha này mà gói ACK của gói tin vừa được gởi lại bị time out thêm lần nữa thì cwnd sẽ bị hạ xuống thành 1 và trở lại giai đoạn Slow Start giống như Tahoe. Tahoe sử dụng timout để phát hiện tắc nghẽn còn Reno sử dụng cả timer và thuật toán Fast-Retransmit để nhận biết tắc nghẽn. Tahoe hạ cwnd xuống còn 1 sau khi mất gói tin, còn Reno hạ cwnd xuống ½ của cwnd hiện tại khi mất gói tin (khi phát hiện 3 duplicate ACK). Ưu điểm Quá trình phục hồi truyền dữ liệu nhanh hơn so với Tahoe (Fast Recovery) vì thường thì thời gian chờ để nhận 3 gói ACK trùng lặp sẽ nhanh hơn là chờ timeout rồi mới send lại gói tin bị mất. Hiệu quả hơn Tahoe. Reno hoạt động tốt khi số lượng gói tin bị mất là tương đối nhỏ. Khuyết điểm Nếu cwnd size của Reno quá nhỏ (nhỏ hơn 4 gói) thì có thể sẽ không nhận đủ 3 gói ACK để chạy thuật toán. Mỗi lần Reno chỉ có thể phát hiện được một gói tin bị mất và không thể nhận biết được trường hợp có nhiều gói tin bị mất. 2.1.3 TCP New Reno Là phiên bản cải tiến thuật toán Re-Trasmit trong giai đoạn Fast Recovery của TCP Reno. 12