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 stateaction 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
- Xem thêm -