Tìm hiểu mạng sdwn trong môi trường không dây và áp dụng giải thuật mab trong việc lựa chọn điểm truy cập mạng
- 58 trang
- file .pdf
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
====o0o====
LUẬN VĂN THẠC SĨ
Tìm hiểu mạng SDWN trong môi trường
không dây và áp dụng giải thuật MAB
trong việc lựa chọn điểm truy cập mạng
ĐÀO ĐỨC HIẾU
[email protected]
Ngành Công nghệ thông tin
Giảng viên hướng dẫn: TS. NGUYỄN ĐỨC TOÀN
Chữ ký của GVHD
Viện: CNTT& Truyền thông
HÀ NỘI, 10/2020
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc
BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ
Họ và tên tác giả luận văn: ĐÀO ĐỨC HIẾU
Đề tài luận văn: Tìm hiểu mạng SDWN trong môi trường không dây và áp
dụng giải thuật MAB trong việc lựa chọn điểm truy cập mạng
Chuyên ngành: Công nghệ thông tin
Mã số SV: CB180196
Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn xác nhận
tác giả đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng ngày
31/10/2020 với các nội dung sau:
- Trình bày cụ thể việc triển khai Local SDN controller như thế nào, ý nghĩa
của nó trong kiến trúc của em là gì? Cách nó vận hành song song cùng với
SDN controller truyền thống?
Trình bày trong mục 2.2. Software Defined Wireless Networking (SDWN)
- Tìm hiểu kỹ hơn về mặt lý thuyết vấn đề/bài toán MAB (chú ý thay đổi tên
gọi, không gọi nó là thuật toán, mà phải gọi là vấn đề hoặc bài toán)
Trình bày trong 1.1.2 Công thức bài toán MAB
- Trình bày kỹ hơn về 2 giải thuật UCB1 và UCB2. Với các kết quả thực
nghiệm thì em có thể tham khảo các bài báo/nghiên cứu khác cũng được,
nhưng phải giải thích và phân tích sâu hơn các kết quả đó
Trình bày trong chương 4: mục 4.1 và 4.2
Kết quả trình bày mục 5.3
Ngày 26 tháng 11 năm 2020
Giáo viên hướng dẫn Tác giả luận văn
CHỦ TỊCH HỘI ĐỒNG
ĐỀ TÀI LUẬN VĂN
Mã đề tài : 2018BMMT-KT05
Theo QĐ số 1684/QĐ-ĐHBK-ĐT-SĐH của Hiệu trưởng trường ĐHBK Hà Nội
ký ngày 16 tháng 10 năm 2019
1. Họ và tên học viên: Đào Đức Hiếu SHHV: CB180196
2. Chuyên ngành: Công nghệ thông tin Lớp: 18BMMT
3. Người hướng dẫn: TS. Nguyễn Đức Toàn
4. Đơn vị: Viện Công nghệ Thông tin - Truyền thông.
5. Tên đề tài (tiếng Việt): Tìm hiểu mạng SDWN trong môi trường không dây
và áp dụng giải thuật MAB trong việc lựa chọn điểm truy cập mạng.
6. Tên đề tài (tiếng Anh): To study SDWN in wireless envirorment and apply
MAB algorithms in selecting network access point.
4/60
LỜI CẢM ƠN
Em xin gửi lời cảm ơn tới các thầy cô giáo giảng viên trường Đại học
Bách Khoa Hà Nội nói chung và các thầy cô giáo giảng viên viện Công nghệ
Thông Tin và Truyền thông nói riêng đã tận tình, nhiệt huyết giảng dạy cho
em để em có nền tảng đại cương vững chắc và kiến thức chuyên môn sâu
sắc, làm hành trang hữu ích trong những chặng hành trình tiếp theo của cuộc
đời.
Đặc biệt em xin gửi lời cảm ơn chân thành tới thầy giáo TS. Nguyễn
Đức Toàn, người đã trực tiếp hướng dẫn, hết lòng giúp đỡ em để em hoàn
thành luận văn này.
Mặc dù đã có nhiều cố gắng trong quá trình thực hiện nhưng do kiến
thức của em còn hạn chế vì vậy luận văn chắc chắn vẫn còn nhiều thiếu sót.
Em xin cảm ơn những ý kiến đóng góp của thầy cô về nội dung và hình thức
luận văn để có thể tiếp tục phát triển hướng nghiên cứu này trong tương lai.
Em xin chân thành cảm ơn!
HỌC VIÊN
Ký và ghi rõ họ tên
Đào Đức Hiếu
5/60
TÓM TẮT NỘI DUNG LUẬN VĂN
1. Cơ sở khoa học và thực tiễn của luận văn
➢ Lý do lựa chọn đề tài.
Với sự phát triển của công nghệ thông tin, đặc biệt là công nghệ máy
tính và công nghệ truyền dẫn, các thiết bị đầu cuối đều được tích hợp hơn
một giao diện kết nối mạng, tăng khả năng kết nối vào mạng mọi lúc mọi
nơi. Mặc dù các thiết bị đầu cuối có nhiều tuyến đường để đi từ nguồn đến
đích, nhưng hiệu quả trong định tuyến chưa được cải thiện. Nguyên nhân
chính là do cơ chế định tuyến truyền thống thường chỉ truyền dữ liệu trên
một tuyến đường tối ưu duy nhất. Việc phân bổ lưu lượng mạng trên nhiều
tuyến đường đến đích có thể giảm thiểu chi phí, tăng hiệu năng và cải thiện
chất lượng dịch vụ mạng.
➢ Tính cấp thiết của đề tài.
Bài toán phân bổ lưu lượng mạng trên nhiều tuyến đường đã và đang
thu hút nhiều nghiên cứu. Một trong các nghiên cứu là cải thiện giao thức
TCP để truyền lưu lượng mạng trên nhiều đường truyền cùng một lúc, gọi là
Multipath TCP. Tuy vậy, việc ứng dụng MPTCP còn chưa phổ biến, còn
nhiều vấn đề về tính tương thích với MPTCP của các ứng dụng đang vận
hành. Để phân bổ lưu lượng trên nhiều tuyến đường mà vẫn sử dụng giao
thức TCP truyền thống vẫn là bài toán mở cho các nhà nghiên cứu. Công
nghệ mạng khả trình (SDWN) cho phép các nhà quản trị điều khiển mạng
bằng phần mềm. Do đó, việc điều khiển mạng có khả năng áp dụng các thuật
toán bổ trợ cho giải thuật tìm đường đi ngắn nhất để nâng cao hiệu năng định
tuyến. Luận văn nghiên cứu về các thuật toán lựa chọn tuyến đường sử dụng
bài toán MAB để nâng cao hiệu quả định tuyến trong mạng SDWN.
2. Mục đích của đề tài (các kết quả cần đạt được):
Mục tiêu của đề tài là tìm hiểu về mạng khả trình Software Defined
Wireless Networking, và một số thuật toán Multi-Armed Bandit. Áp dụng
các thuật toán tìm hiểu được vào điều khiển định tuyến trong mạng SDWN.
Triển khai thí nghiệm để đánh giá hiệu năng định tuyến mạng.
3. Nội dung của luận văn
Luận văn được chia ra làm [05] chương cụ thể như sau:
Chương 1: Đặt vấn đề
Chương 2: Software Defined Wireless Networking (SDWN)
Chương 3: Các phương pháp định tuyến
Chương 4: Giải thuật MAB – Đề xuất giải pháp
Chương 5: Triển khai
6/60
MỤC LỤC
CHƯƠNG 1: ĐẶT VẤN ĐỀ ...................................................................... 11
Mô tả bài toán....................................................................................... 11
Mô hình hệ thống .......................................................................... 11
Công thức bài toán MAB .............................................................. 13
CHƯƠNG 2: SOFTWARE DEFINED WIRELESS NETWORKING
(SDWN) ...................................................................................................... 15
Software Defined Networking (SDN) ................................................. 15
Lớp ứng dụng (Application layer) ................................................ 15
Lớp điều khiển (Control layer) ..................................................... 16
Lớp cơ sở hạ tầng (Infrastructure layer) ....................................... 16
Software Defined Wireless Networking .............................................. 17
SDN CONTROLLER ................................................................... 17
SDN controller truyền thống ......................................................... 17
Local SDN Controller ................................................................... 18
OpenFlow ............................................................................................. 22
Flow tables .................................................................................... 23
Bảng nhóm .................................................................................... 26
Meter Table (Bảng đo) .................................................................. 27
Kênh OpenFlow ............................................................................ 28
2.3.4.1. Tin nhắn OpenFlow ............................................................... 29
OpenFlow switch .......................................................................... 29
Mininet Wifi ......................................................................................... 31
Kiến trúc và thành phần ................................................................ 32
2.4.1.1. Files ........................................................................................ 34
2.4.1.2. Classes .................................................................................... 34
Mô phỏng phương tiện không dây ................................................ 35
2.4.2.1. Kiểm soát giao thông (TC) .................................................... 35
7/60
2.4.2.2. Wmediumd ............................................................................. 36
CHƯƠNG 3: CÁC PHƯƠNG PHÁP ĐỊNH TUYẾN ............................... 38
Các nguyên tắc cơ bản về định tuyến................................................... 38
Định tuyến đường đi ngắn nhất ..................................................... 38
Định tuyến đa đường ..................................................................... 38
3.1.2.1. Equal-cost multi-path (ECMP) .............................................. 39
Định tuyến nguồn .......................................................................... 39
Tiêu chuẩn hiệu suất mạng ................................................................... 40
Chuyển tiếp chủ động........................................................................... 42
CHƯƠNG 4: GIẢI THUẬT MAB – ĐỀ XUẤT GIẢI PHÁP ................... 44
Upper Confidence Bound, version 1 .................................................... 44
Thuật toán dựa trên thuật toán UCB2 .................................................. 45
CHƯƠNG 5: TRIỂN KHAI ........................................................................ 48
Cài đặt LAB- Thu thập dữ liệu ............................................................ 48
Máy ảo mininet-wifi/Ubuntu(VM) ............................................... 48
Khởi tạo mô hình LAB.................................................................. 49
Kịch bản thí nghiệm (di chuyển Mobile) ...................................... 49
Môi trường mô phỏng .......................................................................... 51
Kết quả ................................................................................................. 52
Kết luận ................................................................................................ 57
8/60
DANH MỤC HÌNH VẼ
Hình 1.1 Học theo khe thời gian ................................................................. 12
Hình 2.1 Kiến trúc của SDN ....................................................................... 15
Hình 2.2 Mô hình OpenFlow ...................................................................... 22
Hình 2.3 Bảng OpenFlow ........................................................................... 23
Hình 2.4 Flow Table của OpenFlow cho đến phiên bản 1.3 ...................... 25
Hình 2.5 Bảng nhóm OpenFlow ................................................................. 26
Hình 2.6 Bảng đo ........................................................................................ 28
Hình 2.7 Các loại OpenFlow Message........................................................ 29
Hình 2.8 Các thành phần của một OpenFlow Switch ................................. 30
Hình 2.9 OpenFlow pipeline ....................................................................... 30
Hình 2.10 Các thành phần của Mininet-WiFi ............................................. 32
Hình 2.11 Các thành phần và kết nối trong mạng hai máy chủ được tạo bằng
Mininet-WiFi............................................................................................... 33
Hình 3.1 Thông số hiệu suất mạng ............................................................. 41
Hình 3.2 Mô hình chuyển tiếp chủ động..................................................... 42
Hình 5.1 Một mẫu chạy thuật toán dựa trên khối UCB1 ............................ 53
Hình 5.2 Một mẫu chạy thuật toán dựa trên UCB2 .................................... 53
9/60
TỪ VIẾT TẮT
Từ viết
Tiếng Anh Tiếng Việt
tắt
SDN Software Define Network Mạng khả trình
RTT Round Trip Time Thời gian trọn vòng
SLA Service Level Agreements Thỏa thuận cam kết chất lượng dịch vụ
QoS Quality of Sevices Chất lượng dịch vụ
International
ITU Liên minh Viễn thông Quốc tế
Telecommunication Union
VoIP Voice over IP Truyền thông thoại qua IP
L2 Layer 2 Lớp 2
PF Proactive Forwarding Chuyển tiếp chủ động
Application Programming
API Giao diện lập trình ứng dụng
Interface
Application Specific
ASIC Mạch tích hợp ứng dụng cụ thể
Integrated Circuit
MAB Multi Armed Bandits Kẻ cướp đa vũ trang
Upper Confidence Bound,
UCB1 Giới hạn độ tin cậy trên, phiên bản 1
version 1
VMs Virtual Machines Các máy ảo
TAP Traffic Assignment Problem Vấn đề phân luồng giao thông
OD Origin - Destination Nguồn - Đích
Traffic Assignment by Phân bổ lưu lượng bằng các phân đoạn
TAPAS
Paired Alternative Segments thay thế được ghép nối
BTS Base Transceiver Station Trạm thu phát sóng di động
NAP Network Access Point Điểm truy cập mạng
NSI Network State Information Thông tin trạng thái mạng
QoE Quality of Experience Chất lượng trải nghiệm
RL Reinforcement Learning Học tăng cường
RHC Rate of Handoff Cost Tỷ lệ chi phí chuyển nhượng
Hostapd Host Access Point Daemon
10/60
CHƯƠNG 1: ĐẶT VẤN ĐỀ
Mô tả bài toán
Mô hình hệ thống
Trong những năm gần đây, mạng điều khiển bằng phần mềm SDN
(Software Defined Network) là một trong các công cụ, công nghệ nổi bật
trong việc cung cấp cho các nhà quản trị mạng khả năng quản trị linh hoạt
nhờ vào việc tách biệt việc điều khiển mạng và việc xử lý dữ liệu. Việc điều
khiển mạng được tách khỏi các thiết bị mạng và được thực hiện tập trung
nhờ một phần mềm gọi là SDN Controller. SDN có cái nhìn toàn cục về
mạng do đó có khả năng quản lý mạng một cách linh hoạt. Tuy vậy, công
nghệ SDN được thiết kế cho mạng có dây, việc áp dụng SDN cho mạng
không dây còn nhiều thách thức.
Hiện nay, sự phát triển các mạng không dây bùng nổ mạnh mẽ cả về
chất lượng và số lượng. Mạng di động thế hệ thứ 5 (5G) đã và đang được
triển khai ở nhiều nước. Ở phạm vi nhỏ hơn, các điểm truy cập mạng NAP
(Network Access Point) của mạng Wi-Fi có mặt ở khắp nơi, trong từng hộ
gia đình, trên các phương tiện công cộng, nhà ga, quán cà phê,.. cho phép
người dùng truy cập mạng Internet ở bất cứ đâu. Hơn thế, các thiết bị di động
ngày nay, như máy tính xách tay hay điện thoại di động, được trang bị nhiều
giao diện truy cập mạng, do đó, mỗi thiết bị có thể nhận được sóng của một
hoặc nhiều NAP. Trong cùng một mạng, chẳng hạn mạng Wi-Fi, việc chọn
đường đi, cụ thể là chọn điểm truy cập mạng NAP tốt nhất, để kết nối và
truyền dữ liệu đã được tích hợp vào các thiết bị di động. Tuy vậy, việc chọn
đường trên các mạng không dây không đồng nhất HWN (Heterogeneous
Wireless Network) vẫn còn là bài toán mở [1]. Các nghiên cứu trước đây
thường xử lý bài toán này trong môi trường lý tưởng, trong đó, trạng thái của
các mạng NSI (Network State Information) được giả thiết là đã biết và không
thay đổi. Trong thực tế, do sự không ổn định của các kênh vô tuyến và sự
biến thiên về lưu lượng mạng, thông tin trạng thái của mạng NSI thay đổi
không ngừng, thậm chí là không có – chẳng hạn khi người dùng nằm ngoài
vùng phủ sóng. Do vậy, hầu hết các cách tiếp cận hiện có dựa trên NSI không
thể hoạt động hiệu quả trong thực tế. Để giải quyết thách thức này, luận văn
này mô hình hoá NSI và áp dụng bài toán MAB (Multi Arm Bandit) để nâng
cao hiệu quả chọn đường. Coi tập NAP (Network Access Point) là N, các
11/60
thiết bị UE (User Equipment) có trang bị nhiều giao diện truy cập mạng định
vị trong vùng phủ sóng của N mạng này. Phương pháp chọn đường cho UE
sẽ được thực hiện theo khe thời gian như thể hiện trong Hình 1.1.
Hình 1.1 Học theo khe thời gian
Có thể thấy trong hình, hệ thống hoạt động theo phương thức phân chia theo
khe thời gian. UE chọn một NAP δ(t) ∈ N để truyền vào đầu khe t. Nếu δ(t)
≠ δ(t - 1), quá trình xử lý mạng xảy ra, nếu không, UE tiếp tục truyền trong
NAP đã được kết nối. Biểu thị vectơ x = [ x1, x2, ..., xL ] là vectơ NSI có xl, l
= 1, 2, ..., L có thể liên quan đến các tham số mạng L như băng thông, độ trễ,
v.v. Ở đây, tác giả giả định rằng thời lượng vị trí được chọn thích hợp để các
tham số mạng liên quan trong x gần như không đổi trong một vị trí, trong khi
ở các vị trí khác nhau, chúng là các biến ngẫu nhiên độc lập. Vào cuối khe t,
UE nhận được phần thưởng r(t) = D(xδ(t)(t)), trong đó xn(t) là vectơ tham số
của mạng n trong vị trí thứ t, hàm nhu cầu của người dùng QoE hàm D(x)
ánh xạ vectơ NSI có kinh nghiệm x với phần thưởng của người dùng, cũng
là giá trị QoE. Trong khung thời gian không có mô hình, nơi chỉ có phản hồi
phần thưởng cuối có thể được sử dụng. Nói cách khác, cả NSI và hàm nhu
cầu người dùng đều chưa biết, việc lựa chọn δ(i) chỉ dựa trên quan sát trên
lịch sử hành động truy cập:
𝐴(𝑡) = {𝛿(1), 𝛿(2), . . . , 𝛿(𝑡 − 1)} và phản hồi phần thưởng lịch sử
𝑈(𝑡) = {𝑟(1), 𝑟(2), . . . , 𝑟(𝑡 − 1)}.
Chính sách lựa chọn mạng π thực hiện quyết định lựa chọn mạng cho mỗi vị
trí theo quan sát A(t) và U(t). Để thực hiện việc chuyển mạng, người dùng
trước tiên phải thông báo cho NAP hiện đang được liên kết và ngắt kết nối
12/60
khỏi NAP đó. Sau đó, người dùng phải khám phá và đồng bộ hóa với NAP
mục tiêu để tạo liên kết mới. Cả hai giai đoạn này đều phải chịu chi phí báo
hiệu, phụ thuộc vào các loại mạng không dây, công nghệ vô tuyến, giao thức
cụ thể, v.v. Để tính đến đặc điểm này, ma trận chi phí chuyển nhượng cần
xác định là C ={cm,n}, m, n ∈ N, trong đó cm,n là chi phí báo hiệu khi người
dùng chuyển từ NAP m sang n . Chi phí bằng 0 khi không có chuyển nhượng
nào xảy ra, tức là, cm, n = 0 nếu m = n.
Công thức bài toán MAB
Trong phần này, tác giả mô hình hoá việc lựa chọn mạng theo phương
pháp xác suất học trực tuyến MAB với tham số chính là chi phí chuyển
nhượng mạng. Do sự biến thiên của các thông số mạng, phần thưởng QoE
trong mỗi vị trí là gần như ngẫu nhiên. Vì vậy, hiệu suất của mạng được đánh
giá bằng phần thưởng mong đợi μn = E [r(xn)], Đương nhiên, nếu biết μn, n
∈ N thì mạng tối ưu n∗ cho người dùng là lớn nhất, tức là
𝑛∗ = 𝑎𝑔𝑟 max 𝜇𝑛 (1.1)
𝑛∈𝑁
Một bài toán MAB tổng quát có thể được xây dựng theo kịch bản với N
nhánh của một người chơi. Mỗi lần chơi một số cánh tay n, người chơi sẽ
nhận được một phần thưởng ngẫu nhiên rn sau một số phân phối chưa biết
của cánh tay cụ thể Фn. Mục tiêu của người chơi là tìm một chính sách tối
đa hóa phần thưởng mong đợi dài hạn trong t lần chơi liên tiếp, hoặc tương
đương. Đồng thời giảm thiểu sự hối tiếc, nghĩa là khoảng cách giữa phần
thưởng mong đợi của chính sách và chính sách tối ưu, tức là luôn đóng vai
trò là cánh tay tốt nhất. Áp dụng bài toán MAB vào bài toán lựa chọn mạng,
N mạng có sẵn là cánh tay, người dùng là người chơi, việc truy cập một trong
các NAP trong mỗi vị trí tương đương với việc chơi một cánh tay. Như vậy,
mục tiêu là thiết kế một chính sách tối đa hóa phần thưởng dài hạn. Với chính
sách lựa chọn mạng π, phần thưởng tích lũy dự kiến trong các vị trí tđược
định nghĩa là
𝑡 𝑁
𝐸[𝑆𝜋 (𝑡)] = 𝐸𝜋 [∑ 𝑟(𝑖) = ∑ 𝜇𝑛 𝐸𝜋 [𝑉𝑛 (𝑡)]]
𝑖=1 𝑛=1 (1.2)
trong đó 𝑉𝑛 (𝑡) = ∑𝑡𝑖=1 𝐼 {𝛿(𝑖) = 𝑛} là số lượng khe thời gian mạng n
được chọn trong t vị trí đầu tiên, I{·} là hàm chỉ báo và Eπ[·] có nghĩa là lấy
13/60
kỳ vọng dưới chính sách π. Trong khi đó, chi phí chuyển giao mạng phát sinh
cho việc lựa chọn mạngchính sách ở vị trí thứ t đầu tiên là
𝑡
𝐸[𝐻𝜋 (𝑡)] = 𝐸𝜋 [∑ 𝑐𝛿(𝑖−1),𝛿(𝑖) ]
𝑖=1 (1.3)
Để xác định chi phí chuyển giao mạng trong tổng phần thưởng, cần xác
định phần thưởng là E [Sπ(t)] - ∅ E [Hπ(t)], trong đó 0≤∅≤1 là trọng lượng
của phần thưởng giá cả. Trong bài toán chọn mạng, chính sách lý tưởng được
xác định trong công thức (1.1) và không phát sinh chi phí chuyển nhượng.
Theo đó, một chính sách π’s được định nghĩa là
𝐸[𝑅𝜋 (𝑡)] = 𝐸[𝑆𝜋∗ (𝑡)] − {𝐸[𝑆𝜋 (𝑡)] − ∅𝐸[𝐻𝜋 (𝑡)]}
= ∑ (𝜇𝑛∗ − 𝜇𝑛 )𝐸𝜋 [𝑉𝑛 (𝑡)] + ∅𝐸[𝐻𝜋 (𝑡)]
𝑛≠𝑛∗ (1.4)
Bên cạnh đó, để tránh tình trạng chuyển mạng thường xuyên trong một
thời gian giới hạn, hay "Hiệu ứng bóng bàn" trong việc chuyển mạng, tác giả
xác định một chỉ số chi phí bổ sung, tỷ lệ chi phí chuyển giao (RHC), là chi
phí chuyển giao dự kiến cho mỗi vị trí, như
𝐸[𝐻𝜋 (𝑡)]
𝜌(𝑡) = (1.5)
𝑡
Với hai chỉ số được xác định ở trên, chúng ta sẽ tìm thấy mạng cần được
lựa chọn hoặc chính sách π với sự hối tiếc là nhỏ nhất và RHC
𝑚𝑖𝑛𝜋 𝐸[𝑅𝜋 (𝑡)]
{
𝑚𝑖𝑛𝜋 𝜌(𝑡) (1.6)
14/60
CHƯƠNG 2: SOFTWARE DEFINED WIRELESS
NETWORKING (SDWN)
Công nghệ này về cơ bản tách thành phần điều khiển khỏi thành phần
dữ liệu của mỗi thiết bị mạng (Hình 2.1), tập trung năng lực xử lý điều khiển
lưu lượng, chuyển mạch, định tuyến và Chất lượng dịch vụ (QoS) để đạt
được kiểm soát mạng hiệu quả hơn . Để tuân thủ thỏa thuận cam kết chất
lượng dịch vụ (SLA), mỗi ứng dụng giao tiếp với thành phần điều khiển
thông qua kết nối API (Giao diện lập trình ứng dụng) để thành phần điều
khiển thực hiện các quyết định về chính sách chuyển tiếp gói, xử lý lưu lượng
và QoS phù hợp hơn với yêu cầu dịch vụ trong thời gian thực.
Chương này cung cấp cho các nguyên tắc cơ bản cần thiết về kiến trúc
SDN và OpenFlow. [2].
Software Defined Networking (SDN)
Kiến trúc mạng SDN gồm 3 thành phần.
Hình 2.1 Kiến trúc của SDN
Lớp ứng dụng (Application layer)
Lớp ứng dụng đại diện cho các ứng dụng mạng tương tác với lớp điều
khiển để truyền đạt các yêu cầu của chúng đối với tài nguyên mạng và thực
hiện các thay đổi cụ thể trong mạng, đạt được hành vi mạng mong muốn và
QoS cho một lưu lượng nhất định. Lớp ứng dụng giao tiếp với lớp điều khiển
bằng cách sử dụng các giao diện ứng dụng như North Bound Interface (NBI)
hoặc Java API để thực hiện các thông báo đồng bộ và không đồng bộ. Chúng
15/60
có thể cung cấp sự linh hoạt rộng rãi vì các loại lưu lượng khác nhau có thể
được các ứng dụng mạng khác nhau xử lý riêng biệt, sử dụng cơ sở hạ tầng
mạng như một tài nguyên được chia sẻ. Ví dụ: lưu lượng điều khiển mạng
như thông báo LLDP (Giao thức dữ liệu lớp liên kết), được ứng dụng mạng
riêng xử lý so với lưu lượng dữ liệu thông thường như thông báo ICMP
(Internet Control Message Protocol). Các phương pháp thiết lập đường dẫn
sẽ được thấy trong tài liệu này, là các ứng dụng mạng đang hoạt động ở lớp
này.
Lớp điều khiển (Control layer)
Lớp điều khiển, còn được gọi là Hệ điều hành mạng (NOS) hoặc bộ
điều khiển SDN, là trung gian giữa lớp cơ sở hạ tầng và lớp ứng dụng. Lớp
điều khiển cung cấp cho các ứng dụng một bản tóm tắt về cấu trúc liên kết
mạng, bản kiểm kê các tính năng được hỗ trợ bởi từng thiết bị mạng, thống
kê mạng, theo dõi máy chủ lưu trữ thông tin và thông tin gói. Các ứng dụng
có thể đưa ra quyết định tương ứng, sau đó lớp điều khiển chuyển các quyết
định đó thành các hướng dẫn được tải xuống lớp cơ sở hạ tầng và thực thi
các cài đặt mạng thích hợp cho lưu lượng hiện tại.
Lớp điều khiển được hình thành là tập trung về mặt logic, có nghĩa là
NOS có thể hoạt động dưới một cụm máy chủ vật lý để chia sẻ khối lượng
công việc của hệ thống.
Lớp cơ sở hạ tầng (Infrastructure layer)
Lớp cơ sở hạ tầng bao gồm thành phần dữ liệu của kiến trúc SDN, được
đại diện bởi các thiết bị chuyển tiếp như bộ chuyển mạch và bộ định tuyến.
Chúng chuyển tiếp các gói theo các hướng dẫn mà lớp điều khiển nhận được,
như loại bỏ một gói hoặc gửi gói tin đó ra ngoài thông qua một giao diện đầu
ra. Các thiết bị chuyển tiếp duy trì liên lạc với lớp điều khiển để giữ cho hệ
thống được cập nhật về trạng thái mạng của chúng như các cổng đang hoạt
động, hàng xóm liền kề, các tính năng được hỗ trợ, thông tin bộ đếm và thông
báo sự kiện.
Về mặt logic, các thiết bị chuyển tiếp được xem như một Datapath và
được xác định bởi một Datapath ID (DPID). Thông tin này được bộ điều
khiển SDN sử dụng để giải quyết các hướng dẫn cụ thể cho các thiết bị nhất
định, như các hành động chuyển tiếp hoặc để xác định từng thiết bị mạng
trong phần trừu tượng cấu trúc liên kết.
16/60
Kênh giao tiếp giữa lớp cơ sở hạ tầng và lớp điều khiển được gọi là
Giao diện hướng Nam, được đặc trưng bởi một số giao thức truyền thông
thực hiện tương tác giữa bộ điều khiển SDN và các đường dẫn dữ liệu. Giao
thức SouthBound phổ biến nhất được sử dụng là OpenFlow, được hầu hết
các nhà cung cấp chấp nhận vì OpenFlow được phát triển liên tục để hoạt
động cho việc điều khiển mạng và truyền thông SouthBound.
Software Defined Wireless Networking
Trong các mạng SDN, một điều khiển tập trung thường được sử dụng
để cung cấp cái nhìn toàn cầu về mạng và đơn giản hóa hoạt động mạng cũng
như mạng khả năng lập trình. Tuy nhiên, trong mô hình tập trung, việc kiểm
soát đường dẫn giữa các thiết bị mạng và bộ điều khiển có thể là điểm thất
bại duy nhất hoặc điểm nghẽn tiềm ẩn. Do đó, SDN controller truyền thống
đã được mở rộng và sau đó được nhúng vào mọi nút, nhằm mục đích giảm
nguy cơ mất kết nối với bộ điều khiển và sự chậm trễ trong quá trình truyền
lệnh từ bộ điều khiển đến các thiết bị. Mô hình này cũng cho phép sử dụng
lợi ích của SDN trong môi trường không dây.Ví dụ: khả năng phục hồi của
hệ thống đã được cải thiện bởi chuyển một kết nối đang diễn ra từ giao diện
vật lý sang một cái khác. Hiệu suất của hệ thống được đánh giá trong một
thử nghiệm thực tế và kết quả thử nghiệm cho thấy hệ thống được trang bị
local SDN controller là giải pháp đầy hứa hẹn để chuyển giao trong mạng
không dây. [3]
SDN CONTROLLER
SDN controller truyền thống
Kiến trúc SDN bao gồm ba lớp như được hiển thị trong (Hình 2.2). Lớp
thấp nhất là Mặt phẳng dữ liệu bao gồm chuyển tiếp các thiết bị mạng, tức
là các thiết bị chuyển mạch, để đáp ứng vớichuyển tiếp dữ liệu và thu thập
số liệu thống kê. Các công tắc là thường được sản xuất bởi các công ty khác
nhau và được trang bị hệ thống hoạt động tư nhân của họ. Do đó, mạng quản
trị viên phải tuân theo hướng dẫn của công ty để định cấu hình công tắc để
chỉ cần chuyển lưu lượng từ các cổng đầu vào sang các cổng ra. Ngược lại,
trong mạng SDN, bộ chuyển mạch thực hiện chuyển tiếp các gói dựa trên
các quy tắc luồng được lưu giữ trong cơ sở dữ liệu hoặc bảng luồng. Quy tắc
luồng hoặc mục nhập luồng là được lắp vào, sửa đổi hoặc loại bỏ bởi mặt
phẳng điều khiển thông qua một kênh giao tiếp được gọi là giao diện hướng
17/60
Nam (SBI). Giao diện thường sử dụng một giao thức có tên OpenFlow cho
giao tiếp giữa Mặt phẳng dữ liệu và Mặt phẳng điều khiển. Các công tắc hỗ
trợ OpenFlow thường yêu cầu bộ điều khiển với PACKET_IN thông báo khi
họ không tìm thấy kết quả phù hợp quy tắc luồng cho các gói đến. Người
điều khiển sau đó trả lời bằng cách yêu cầu bộ chuyển mạch gán các hành
động cho các gói. Đối với ví dụ, bộ điều khiển trả lời bằng một thông báo
FLOWMOD, là một trong những thông báo chính, để sửa đổi trạng thái của
công tắc điện
Hình 2.2 Kiến trúc SDN
Trên mặt phẳng Điều khiển, bộ điều khiển không chỉ chịu trách nhiệm
để kiểm soát hoạt động mạng, nhưng cũng lắng nghe yêu cầu từ các ứng
dụng trong Mặt phẳng ứng dụng. Các bộ điều khiển giải thích yêu cầu của
ứng dụng và vượt qua các hàng đợi tương ứng với mặt phẳng dữ liệu. Mặt
phẳng điều khiển cũng cung cấp các dịch vụ mạng như chính sách quản lý
hoặc chất lượng của dịch vụ cho các ứng dụng. Bộ điều khiển giao tiếp với
các ứng dụng thông qua giao diện ứng dụng - bộ điều khiển hoặc giao diện
hướng Bắc (NBI). Đặc tả SDN không chuẩn hóa NBI. SDN cho phép phần
mềm điều khiển tự cung cấp phương pháp nói chuyện với các ứng dụng.
Local SDN Controller
Thông thường, SDN controller tập trung chỉ cần giao tiếp với công tắc
OpenFlow và xử lý mạng sự kiện do họ hỏi vì SDN controller có chế độ xem
toàn cầu của mạng. Tuy nhiên, khi bộ điều khiển và công tắc OpenFlow được
18/60
triển khai trên cùng một nút, bộ điều khiển không biết gì về cấu trúc liên kết
của toàn bộ mạng. Thay vào đó, local SDN controller có thông tin mạng cục
bộ (tức là yêu cầu ARP hoặc RSSI) không được công tắc xử lý. Qua đó, trong
công việc này, một Local SDN Controller đã được phát triển để cho phép
Controller xử lý các yêu cầu chuyển đổi cũng như hành vi mạng cục bộ.
Logic điều khiển của nút di động dựa trên SDN, trong đó SDN
Controller truyền thống và một Local SDN controller được nhúng.
Hình 2.3. Logic điều khiển nút di động dựa trên SDN
Nút có thể là máy tính bảng, điện thoại di động hoặc máy tính xách tay.
Ở trên cùng, bộ điều khiển ban đầu và phần mở rộng chúng đang kiểm soát
hành vi mạng cục bộ cho nút. Các bộ SDN Controller truyền thống thông
qua giao thức OpenFlow (ví dụ Open vSwitch – OVS). Ở bên phải, Local
SDN controller thu thập trực tiếp thông tin mạng từ các giao diện mạng vật
lý. Local SDN controller là được phát triển để có thể tùy chỉnh cấu hình mạng
của bất kỳ giao diện nào. Thông tin thu thập được lưu trữ trong cơ sở dữ liệu
để SDN controller truyền thống có thể đọc và rõ hơn về cấu trúc liên kết
mạng. Ở giữa, OVS điều hướng lưu lượng mạng vào và ra khỏi nút. Local
SDN controller cung cấp một hoặc nhiều cầu ảo hoạt động như một hoặc
nhiều điểm trung gian giao diện nằm giữa giao diện vật lý và các ứng dụng.
Ở phía dưới, tất cả các giao diện mạng vật lý đều được cấu hình để trở thành
19/60
các cổng chuyển đổi của OVS. Một cây cầu có thể bao gồm một hoặc nhiều
giao diện vật lý nhưng giao diện không thể thuộc về đến nhiều hơn một cây
cầu.
Yêu cầu thiết kế:
a) Local SDN controller phải hoạt động với mọi SDN controller hiện
có:
Mặc dù SDN Controller hiện tại có thiết kế riêngvới các API khác nhau,
Local SDN controller phải có thể hoạt động với họ trong mạng SDN. Local
SDN controller, không có kênh giao tiếp ngoại trừ kênh có công tắc, có thể
đọc thông tin mạng bất cứ lúc nào. Nếu thu thập thông tin đủ lớn, SDN
Controller có thể có đủ kiến thức về cấu trúc liên kết mạng. Điều đó là có
thể vì local controller có thể trao đổi và cập nhật cơ sở dữ liệu đến bất kỳ
nút nào mà local controller kết nối.
Attributes
Tag name
Name Switch port IP MAC Status ID Key
Connection X X
Media X X X
Bridge X X X X X
Interface X X X X X
Bảng 1: Bảng dữ liệu trạng thái mạng
Bảng 1, cho thấynội dung chính của tệp, trong đó, tất cả các cấu hình
mạng được mô tả. Ví dụ:
Thẻ Connection: là để trình bày tên nút và trạng thái kết nối từ nút cục
bộ đến các nút khác. Thẻ Connection có hai thuộc tính tên là Tên và Trạng
thái được đánh dấu bằng X.
Thẻ Media: hiển thị phương thức mà nút cục bộ đang sử dụng để kết
nối với bên ngoài. Thẻ Media có ba thuộc tính Name, ID và Key. Thuộc tính
Name hiển thị tên của kết nối, nghĩa là Wi-Fi hoặc Bluetooth, trong khi ID
hiển thị SSID của AP hoặc địa chỉ MAC của Bluetooth master và Key chứa
chuỗi bảo mật để xác thực.
20/60
====o0o====
LUẬN VĂN THẠC SĨ
Tìm hiểu mạng SDWN trong môi trường
không dây và áp dụng giải thuật MAB
trong việc lựa chọn điểm truy cập mạng
ĐÀO ĐỨC HIẾU
[email protected]
Ngành Công nghệ thông tin
Giảng viên hướng dẫn: TS. NGUYỄN ĐỨC TOÀN
Chữ ký của GVHD
Viện: CNTT& Truyền thông
HÀ NỘI, 10/2020
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc
BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ
Họ và tên tác giả luận văn: ĐÀO ĐỨC HIẾU
Đề tài luận văn: Tìm hiểu mạng SDWN trong môi trường không dây và áp
dụng giải thuật MAB trong việc lựa chọn điểm truy cập mạng
Chuyên ngành: Công nghệ thông tin
Mã số SV: CB180196
Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn xác nhận
tác giả đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng ngày
31/10/2020 với các nội dung sau:
- Trình bày cụ thể việc triển khai Local SDN controller như thế nào, ý nghĩa
của nó trong kiến trúc của em là gì? Cách nó vận hành song song cùng với
SDN controller truyền thống?
Trình bày trong mục 2.2. Software Defined Wireless Networking (SDWN)
- Tìm hiểu kỹ hơn về mặt lý thuyết vấn đề/bài toán MAB (chú ý thay đổi tên
gọi, không gọi nó là thuật toán, mà phải gọi là vấn đề hoặc bài toán)
Trình bày trong 1.1.2 Công thức bài toán MAB
- Trình bày kỹ hơn về 2 giải thuật UCB1 và UCB2. Với các kết quả thực
nghiệm thì em có thể tham khảo các bài báo/nghiên cứu khác cũng được,
nhưng phải giải thích và phân tích sâu hơn các kết quả đó
Trình bày trong chương 4: mục 4.1 và 4.2
Kết quả trình bày mục 5.3
Ngày 26 tháng 11 năm 2020
Giáo viên hướng dẫn Tác giả luận văn
CHỦ TỊCH HỘI ĐỒNG
ĐỀ TÀI LUẬN VĂN
Mã đề tài : 2018BMMT-KT05
Theo QĐ số 1684/QĐ-ĐHBK-ĐT-SĐH của Hiệu trưởng trường ĐHBK Hà Nội
ký ngày 16 tháng 10 năm 2019
1. Họ và tên học viên: Đào Đức Hiếu SHHV: CB180196
2. Chuyên ngành: Công nghệ thông tin Lớp: 18BMMT
3. Người hướng dẫn: TS. Nguyễn Đức Toàn
4. Đơn vị: Viện Công nghệ Thông tin - Truyền thông.
5. Tên đề tài (tiếng Việt): Tìm hiểu mạng SDWN trong môi trường không dây
và áp dụng giải thuật MAB trong việc lựa chọn điểm truy cập mạng.
6. Tên đề tài (tiếng Anh): To study SDWN in wireless envirorment and apply
MAB algorithms in selecting network access point.
4/60
LỜI CẢM ƠN
Em xin gửi lời cảm ơn tới các thầy cô giáo giảng viên trường Đại học
Bách Khoa Hà Nội nói chung và các thầy cô giáo giảng viên viện Công nghệ
Thông Tin và Truyền thông nói riêng đã tận tình, nhiệt huyết giảng dạy cho
em để em có nền tảng đại cương vững chắc và kiến thức chuyên môn sâu
sắc, làm hành trang hữu ích trong những chặng hành trình tiếp theo của cuộc
đời.
Đặc biệt em xin gửi lời cảm ơn chân thành tới thầy giáo TS. Nguyễn
Đức Toàn, người đã trực tiếp hướng dẫn, hết lòng giúp đỡ em để em hoàn
thành luận văn này.
Mặc dù đã có nhiều cố gắng trong quá trình thực hiện nhưng do kiến
thức của em còn hạn chế vì vậy luận văn chắc chắn vẫn còn nhiều thiếu sót.
Em xin cảm ơn những ý kiến đóng góp của thầy cô về nội dung và hình thức
luận văn để có thể tiếp tục phát triển hướng nghiên cứu này trong tương lai.
Em xin chân thành cảm ơn!
HỌC VIÊN
Ký và ghi rõ họ tên
Đào Đức Hiếu
5/60
TÓM TẮT NỘI DUNG LUẬN VĂN
1. Cơ sở khoa học và thực tiễn của luận văn
➢ Lý do lựa chọn đề tài.
Với sự phát triển của công nghệ thông tin, đặc biệt là công nghệ máy
tính và công nghệ truyền dẫn, các thiết bị đầu cuối đều được tích hợp hơn
một giao diện kết nối mạng, tăng khả năng kết nối vào mạng mọi lúc mọi
nơi. Mặc dù các thiết bị đầu cuối có nhiều tuyến đường để đi từ nguồn đến
đích, nhưng hiệu quả trong định tuyến chưa được cải thiện. Nguyên nhân
chính là do cơ chế định tuyến truyền thống thường chỉ truyền dữ liệu trên
một tuyến đường tối ưu duy nhất. Việc phân bổ lưu lượng mạng trên nhiều
tuyến đường đến đích có thể giảm thiểu chi phí, tăng hiệu năng và cải thiện
chất lượng dịch vụ mạng.
➢ Tính cấp thiết của đề tài.
Bài toán phân bổ lưu lượng mạng trên nhiều tuyến đường đã và đang
thu hút nhiều nghiên cứu. Một trong các nghiên cứu là cải thiện giao thức
TCP để truyền lưu lượng mạng trên nhiều đường truyền cùng một lúc, gọi là
Multipath TCP. Tuy vậy, việc ứng dụng MPTCP còn chưa phổ biến, còn
nhiều vấn đề về tính tương thích với MPTCP của các ứng dụng đang vận
hành. Để phân bổ lưu lượng trên nhiều tuyến đường mà vẫn sử dụng giao
thức TCP truyền thống vẫn là bài toán mở cho các nhà nghiên cứu. Công
nghệ mạng khả trình (SDWN) cho phép các nhà quản trị điều khiển mạng
bằng phần mềm. Do đó, việc điều khiển mạng có khả năng áp dụng các thuật
toán bổ trợ cho giải thuật tìm đường đi ngắn nhất để nâng cao hiệu năng định
tuyến. Luận văn nghiên cứu về các thuật toán lựa chọn tuyến đường sử dụng
bài toán MAB để nâng cao hiệu quả định tuyến trong mạng SDWN.
2. Mục đích của đề tài (các kết quả cần đạt được):
Mục tiêu của đề tài là tìm hiểu về mạng khả trình Software Defined
Wireless Networking, và một số thuật toán Multi-Armed Bandit. Áp dụng
các thuật toán tìm hiểu được vào điều khiển định tuyến trong mạng SDWN.
Triển khai thí nghiệm để đánh giá hiệu năng định tuyến mạng.
3. Nội dung của luận văn
Luận văn được chia ra làm [05] chương cụ thể như sau:
Chương 1: Đặt vấn đề
Chương 2: Software Defined Wireless Networking (SDWN)
Chương 3: Các phương pháp định tuyến
Chương 4: Giải thuật MAB – Đề xuất giải pháp
Chương 5: Triển khai
6/60
MỤC LỤC
CHƯƠNG 1: ĐẶT VẤN ĐỀ ...................................................................... 11
Mô tả bài toán....................................................................................... 11
Mô hình hệ thống .......................................................................... 11
Công thức bài toán MAB .............................................................. 13
CHƯƠNG 2: SOFTWARE DEFINED WIRELESS NETWORKING
(SDWN) ...................................................................................................... 15
Software Defined Networking (SDN) ................................................. 15
Lớp ứng dụng (Application layer) ................................................ 15
Lớp điều khiển (Control layer) ..................................................... 16
Lớp cơ sở hạ tầng (Infrastructure layer) ....................................... 16
Software Defined Wireless Networking .............................................. 17
SDN CONTROLLER ................................................................... 17
SDN controller truyền thống ......................................................... 17
Local SDN Controller ................................................................... 18
OpenFlow ............................................................................................. 22
Flow tables .................................................................................... 23
Bảng nhóm .................................................................................... 26
Meter Table (Bảng đo) .................................................................. 27
Kênh OpenFlow ............................................................................ 28
2.3.4.1. Tin nhắn OpenFlow ............................................................... 29
OpenFlow switch .......................................................................... 29
Mininet Wifi ......................................................................................... 31
Kiến trúc và thành phần ................................................................ 32
2.4.1.1. Files ........................................................................................ 34
2.4.1.2. Classes .................................................................................... 34
Mô phỏng phương tiện không dây ................................................ 35
2.4.2.1. Kiểm soát giao thông (TC) .................................................... 35
7/60
2.4.2.2. Wmediumd ............................................................................. 36
CHƯƠNG 3: CÁC PHƯƠNG PHÁP ĐỊNH TUYẾN ............................... 38
Các nguyên tắc cơ bản về định tuyến................................................... 38
Định tuyến đường đi ngắn nhất ..................................................... 38
Định tuyến đa đường ..................................................................... 38
3.1.2.1. Equal-cost multi-path (ECMP) .............................................. 39
Định tuyến nguồn .......................................................................... 39
Tiêu chuẩn hiệu suất mạng ................................................................... 40
Chuyển tiếp chủ động........................................................................... 42
CHƯƠNG 4: GIẢI THUẬT MAB – ĐỀ XUẤT GIẢI PHÁP ................... 44
Upper Confidence Bound, version 1 .................................................... 44
Thuật toán dựa trên thuật toán UCB2 .................................................. 45
CHƯƠNG 5: TRIỂN KHAI ........................................................................ 48
Cài đặt LAB- Thu thập dữ liệu ............................................................ 48
Máy ảo mininet-wifi/Ubuntu(VM) ............................................... 48
Khởi tạo mô hình LAB.................................................................. 49
Kịch bản thí nghiệm (di chuyển Mobile) ...................................... 49
Môi trường mô phỏng .......................................................................... 51
Kết quả ................................................................................................. 52
Kết luận ................................................................................................ 57
8/60
DANH MỤC HÌNH VẼ
Hình 1.1 Học theo khe thời gian ................................................................. 12
Hình 2.1 Kiến trúc của SDN ....................................................................... 15
Hình 2.2 Mô hình OpenFlow ...................................................................... 22
Hình 2.3 Bảng OpenFlow ........................................................................... 23
Hình 2.4 Flow Table của OpenFlow cho đến phiên bản 1.3 ...................... 25
Hình 2.5 Bảng nhóm OpenFlow ................................................................. 26
Hình 2.6 Bảng đo ........................................................................................ 28
Hình 2.7 Các loại OpenFlow Message........................................................ 29
Hình 2.8 Các thành phần của một OpenFlow Switch ................................. 30
Hình 2.9 OpenFlow pipeline ....................................................................... 30
Hình 2.10 Các thành phần của Mininet-WiFi ............................................. 32
Hình 2.11 Các thành phần và kết nối trong mạng hai máy chủ được tạo bằng
Mininet-WiFi............................................................................................... 33
Hình 3.1 Thông số hiệu suất mạng ............................................................. 41
Hình 3.2 Mô hình chuyển tiếp chủ động..................................................... 42
Hình 5.1 Một mẫu chạy thuật toán dựa trên khối UCB1 ............................ 53
Hình 5.2 Một mẫu chạy thuật toán dựa trên UCB2 .................................... 53
9/60
TỪ VIẾT TẮT
Từ viết
Tiếng Anh Tiếng Việt
tắt
SDN Software Define Network Mạng khả trình
RTT Round Trip Time Thời gian trọn vòng
SLA Service Level Agreements Thỏa thuận cam kết chất lượng dịch vụ
QoS Quality of Sevices Chất lượng dịch vụ
International
ITU Liên minh Viễn thông Quốc tế
Telecommunication Union
VoIP Voice over IP Truyền thông thoại qua IP
L2 Layer 2 Lớp 2
PF Proactive Forwarding Chuyển tiếp chủ động
Application Programming
API Giao diện lập trình ứng dụng
Interface
Application Specific
ASIC Mạch tích hợp ứng dụng cụ thể
Integrated Circuit
MAB Multi Armed Bandits Kẻ cướp đa vũ trang
Upper Confidence Bound,
UCB1 Giới hạn độ tin cậy trên, phiên bản 1
version 1
VMs Virtual Machines Các máy ảo
TAP Traffic Assignment Problem Vấn đề phân luồng giao thông
OD Origin - Destination Nguồn - Đích
Traffic Assignment by Phân bổ lưu lượng bằng các phân đoạn
TAPAS
Paired Alternative Segments thay thế được ghép nối
BTS Base Transceiver Station Trạm thu phát sóng di động
NAP Network Access Point Điểm truy cập mạng
NSI Network State Information Thông tin trạng thái mạng
QoE Quality of Experience Chất lượng trải nghiệm
RL Reinforcement Learning Học tăng cường
RHC Rate of Handoff Cost Tỷ lệ chi phí chuyển nhượng
Hostapd Host Access Point Daemon
10/60
CHƯƠNG 1: ĐẶT VẤN ĐỀ
Mô tả bài toán
Mô hình hệ thống
Trong những năm gần đây, mạng điều khiển bằng phần mềm SDN
(Software Defined Network) là một trong các công cụ, công nghệ nổi bật
trong việc cung cấp cho các nhà quản trị mạng khả năng quản trị linh hoạt
nhờ vào việc tách biệt việc điều khiển mạng và việc xử lý dữ liệu. Việc điều
khiển mạng được tách khỏi các thiết bị mạng và được thực hiện tập trung
nhờ một phần mềm gọi là SDN Controller. SDN có cái nhìn toàn cục về
mạng do đó có khả năng quản lý mạng một cách linh hoạt. Tuy vậy, công
nghệ SDN được thiết kế cho mạng có dây, việc áp dụng SDN cho mạng
không dây còn nhiều thách thức.
Hiện nay, sự phát triển các mạng không dây bùng nổ mạnh mẽ cả về
chất lượng và số lượng. Mạng di động thế hệ thứ 5 (5G) đã và đang được
triển khai ở nhiều nước. Ở phạm vi nhỏ hơn, các điểm truy cập mạng NAP
(Network Access Point) của mạng Wi-Fi có mặt ở khắp nơi, trong từng hộ
gia đình, trên các phương tiện công cộng, nhà ga, quán cà phê,.. cho phép
người dùng truy cập mạng Internet ở bất cứ đâu. Hơn thế, các thiết bị di động
ngày nay, như máy tính xách tay hay điện thoại di động, được trang bị nhiều
giao diện truy cập mạng, do đó, mỗi thiết bị có thể nhận được sóng của một
hoặc nhiều NAP. Trong cùng một mạng, chẳng hạn mạng Wi-Fi, việc chọn
đường đi, cụ thể là chọn điểm truy cập mạng NAP tốt nhất, để kết nối và
truyền dữ liệu đã được tích hợp vào các thiết bị di động. Tuy vậy, việc chọn
đường trên các mạng không dây không đồng nhất HWN (Heterogeneous
Wireless Network) vẫn còn là bài toán mở [1]. Các nghiên cứu trước đây
thường xử lý bài toán này trong môi trường lý tưởng, trong đó, trạng thái của
các mạng NSI (Network State Information) được giả thiết là đã biết và không
thay đổi. Trong thực tế, do sự không ổn định của các kênh vô tuyến và sự
biến thiên về lưu lượng mạng, thông tin trạng thái của mạng NSI thay đổi
không ngừng, thậm chí là không có – chẳng hạn khi người dùng nằm ngoài
vùng phủ sóng. Do vậy, hầu hết các cách tiếp cận hiện có dựa trên NSI không
thể hoạt động hiệu quả trong thực tế. Để giải quyết thách thức này, luận văn
này mô hình hoá NSI và áp dụng bài toán MAB (Multi Arm Bandit) để nâng
cao hiệu quả chọn đường. Coi tập NAP (Network Access Point) là N, các
11/60
thiết bị UE (User Equipment) có trang bị nhiều giao diện truy cập mạng định
vị trong vùng phủ sóng của N mạng này. Phương pháp chọn đường cho UE
sẽ được thực hiện theo khe thời gian như thể hiện trong Hình 1.1.
Hình 1.1 Học theo khe thời gian
Có thể thấy trong hình, hệ thống hoạt động theo phương thức phân chia theo
khe thời gian. UE chọn một NAP δ(t) ∈ N để truyền vào đầu khe t. Nếu δ(t)
≠ δ(t - 1), quá trình xử lý mạng xảy ra, nếu không, UE tiếp tục truyền trong
NAP đã được kết nối. Biểu thị vectơ x = [ x1, x2, ..., xL ] là vectơ NSI có xl, l
= 1, 2, ..., L có thể liên quan đến các tham số mạng L như băng thông, độ trễ,
v.v. Ở đây, tác giả giả định rằng thời lượng vị trí được chọn thích hợp để các
tham số mạng liên quan trong x gần như không đổi trong một vị trí, trong khi
ở các vị trí khác nhau, chúng là các biến ngẫu nhiên độc lập. Vào cuối khe t,
UE nhận được phần thưởng r(t) = D(xδ(t)(t)), trong đó xn(t) là vectơ tham số
của mạng n trong vị trí thứ t, hàm nhu cầu của người dùng QoE hàm D(x)
ánh xạ vectơ NSI có kinh nghiệm x với phần thưởng của người dùng, cũng
là giá trị QoE. Trong khung thời gian không có mô hình, nơi chỉ có phản hồi
phần thưởng cuối có thể được sử dụng. Nói cách khác, cả NSI và hàm nhu
cầu người dùng đều chưa biết, việc lựa chọn δ(i) chỉ dựa trên quan sát trên
lịch sử hành động truy cập:
𝐴(𝑡) = {𝛿(1), 𝛿(2), . . . , 𝛿(𝑡 − 1)} và phản hồi phần thưởng lịch sử
𝑈(𝑡) = {𝑟(1), 𝑟(2), . . . , 𝑟(𝑡 − 1)}.
Chính sách lựa chọn mạng π thực hiện quyết định lựa chọn mạng cho mỗi vị
trí theo quan sát A(t) và U(t). Để thực hiện việc chuyển mạng, người dùng
trước tiên phải thông báo cho NAP hiện đang được liên kết và ngắt kết nối
12/60
khỏi NAP đó. Sau đó, người dùng phải khám phá và đồng bộ hóa với NAP
mục tiêu để tạo liên kết mới. Cả hai giai đoạn này đều phải chịu chi phí báo
hiệu, phụ thuộc vào các loại mạng không dây, công nghệ vô tuyến, giao thức
cụ thể, v.v. Để tính đến đặc điểm này, ma trận chi phí chuyển nhượng cần
xác định là C ={cm,n}, m, n ∈ N, trong đó cm,n là chi phí báo hiệu khi người
dùng chuyển từ NAP m sang n . Chi phí bằng 0 khi không có chuyển nhượng
nào xảy ra, tức là, cm, n = 0 nếu m = n.
Công thức bài toán MAB
Trong phần này, tác giả mô hình hoá việc lựa chọn mạng theo phương
pháp xác suất học trực tuyến MAB với tham số chính là chi phí chuyển
nhượng mạng. Do sự biến thiên của các thông số mạng, phần thưởng QoE
trong mỗi vị trí là gần như ngẫu nhiên. Vì vậy, hiệu suất của mạng được đánh
giá bằng phần thưởng mong đợi μn = E [r(xn)], Đương nhiên, nếu biết μn, n
∈ N thì mạng tối ưu n∗ cho người dùng là lớn nhất, tức là
𝑛∗ = 𝑎𝑔𝑟 max 𝜇𝑛 (1.1)
𝑛∈𝑁
Một bài toán MAB tổng quát có thể được xây dựng theo kịch bản với N
nhánh của một người chơi. Mỗi lần chơi một số cánh tay n, người chơi sẽ
nhận được một phần thưởng ngẫu nhiên rn sau một số phân phối chưa biết
của cánh tay cụ thể Фn. Mục tiêu của người chơi là tìm một chính sách tối
đa hóa phần thưởng mong đợi dài hạn trong t lần chơi liên tiếp, hoặc tương
đương. Đồng thời giảm thiểu sự hối tiếc, nghĩa là khoảng cách giữa phần
thưởng mong đợi của chính sách và chính sách tối ưu, tức là luôn đóng vai
trò là cánh tay tốt nhất. Áp dụng bài toán MAB vào bài toán lựa chọn mạng,
N mạng có sẵn là cánh tay, người dùng là người chơi, việc truy cập một trong
các NAP trong mỗi vị trí tương đương với việc chơi một cánh tay. Như vậy,
mục tiêu là thiết kế một chính sách tối đa hóa phần thưởng dài hạn. Với chính
sách lựa chọn mạng π, phần thưởng tích lũy dự kiến trong các vị trí tđược
định nghĩa là
𝑡 𝑁
𝐸[𝑆𝜋 (𝑡)] = 𝐸𝜋 [∑ 𝑟(𝑖) = ∑ 𝜇𝑛 𝐸𝜋 [𝑉𝑛 (𝑡)]]
𝑖=1 𝑛=1 (1.2)
trong đó 𝑉𝑛 (𝑡) = ∑𝑡𝑖=1 𝐼 {𝛿(𝑖) = 𝑛} là số lượng khe thời gian mạng n
được chọn trong t vị trí đầu tiên, I{·} là hàm chỉ báo và Eπ[·] có nghĩa là lấy
13/60
kỳ vọng dưới chính sách π. Trong khi đó, chi phí chuyển giao mạng phát sinh
cho việc lựa chọn mạngchính sách ở vị trí thứ t đầu tiên là
𝑡
𝐸[𝐻𝜋 (𝑡)] = 𝐸𝜋 [∑ 𝑐𝛿(𝑖−1),𝛿(𝑖) ]
𝑖=1 (1.3)
Để xác định chi phí chuyển giao mạng trong tổng phần thưởng, cần xác
định phần thưởng là E [Sπ(t)] - ∅ E [Hπ(t)], trong đó 0≤∅≤1 là trọng lượng
của phần thưởng giá cả. Trong bài toán chọn mạng, chính sách lý tưởng được
xác định trong công thức (1.1) và không phát sinh chi phí chuyển nhượng.
Theo đó, một chính sách π’s được định nghĩa là
𝐸[𝑅𝜋 (𝑡)] = 𝐸[𝑆𝜋∗ (𝑡)] − {𝐸[𝑆𝜋 (𝑡)] − ∅𝐸[𝐻𝜋 (𝑡)]}
= ∑ (𝜇𝑛∗ − 𝜇𝑛 )𝐸𝜋 [𝑉𝑛 (𝑡)] + ∅𝐸[𝐻𝜋 (𝑡)]
𝑛≠𝑛∗ (1.4)
Bên cạnh đó, để tránh tình trạng chuyển mạng thường xuyên trong một
thời gian giới hạn, hay "Hiệu ứng bóng bàn" trong việc chuyển mạng, tác giả
xác định một chỉ số chi phí bổ sung, tỷ lệ chi phí chuyển giao (RHC), là chi
phí chuyển giao dự kiến cho mỗi vị trí, như
𝐸[𝐻𝜋 (𝑡)]
𝜌(𝑡) = (1.5)
𝑡
Với hai chỉ số được xác định ở trên, chúng ta sẽ tìm thấy mạng cần được
lựa chọn hoặc chính sách π với sự hối tiếc là nhỏ nhất và RHC
𝑚𝑖𝑛𝜋 𝐸[𝑅𝜋 (𝑡)]
{
𝑚𝑖𝑛𝜋 𝜌(𝑡) (1.6)
14/60
CHƯƠNG 2: SOFTWARE DEFINED WIRELESS
NETWORKING (SDWN)
Công nghệ này về cơ bản tách thành phần điều khiển khỏi thành phần
dữ liệu của mỗi thiết bị mạng (Hình 2.1), tập trung năng lực xử lý điều khiển
lưu lượng, chuyển mạch, định tuyến và Chất lượng dịch vụ (QoS) để đạt
được kiểm soát mạng hiệu quả hơn . Để tuân thủ thỏa thuận cam kết chất
lượng dịch vụ (SLA), mỗi ứng dụng giao tiếp với thành phần điều khiển
thông qua kết nối API (Giao diện lập trình ứng dụng) để thành phần điều
khiển thực hiện các quyết định về chính sách chuyển tiếp gói, xử lý lưu lượng
và QoS phù hợp hơn với yêu cầu dịch vụ trong thời gian thực.
Chương này cung cấp cho các nguyên tắc cơ bản cần thiết về kiến trúc
SDN và OpenFlow. [2].
Software Defined Networking (SDN)
Kiến trúc mạng SDN gồm 3 thành phần.
Hình 2.1 Kiến trúc của SDN
Lớp ứng dụng (Application layer)
Lớp ứng dụng đại diện cho các ứng dụng mạng tương tác với lớp điều
khiển để truyền đạt các yêu cầu của chúng đối với tài nguyên mạng và thực
hiện các thay đổi cụ thể trong mạng, đạt được hành vi mạng mong muốn và
QoS cho một lưu lượng nhất định. Lớp ứng dụng giao tiếp với lớp điều khiển
bằng cách sử dụng các giao diện ứng dụng như North Bound Interface (NBI)
hoặc Java API để thực hiện các thông báo đồng bộ và không đồng bộ. Chúng
15/60
có thể cung cấp sự linh hoạt rộng rãi vì các loại lưu lượng khác nhau có thể
được các ứng dụng mạng khác nhau xử lý riêng biệt, sử dụng cơ sở hạ tầng
mạng như một tài nguyên được chia sẻ. Ví dụ: lưu lượng điều khiển mạng
như thông báo LLDP (Giao thức dữ liệu lớp liên kết), được ứng dụng mạng
riêng xử lý so với lưu lượng dữ liệu thông thường như thông báo ICMP
(Internet Control Message Protocol). Các phương pháp thiết lập đường dẫn
sẽ được thấy trong tài liệu này, là các ứng dụng mạng đang hoạt động ở lớp
này.
Lớp điều khiển (Control layer)
Lớp điều khiển, còn được gọi là Hệ điều hành mạng (NOS) hoặc bộ
điều khiển SDN, là trung gian giữa lớp cơ sở hạ tầng và lớp ứng dụng. Lớp
điều khiển cung cấp cho các ứng dụng một bản tóm tắt về cấu trúc liên kết
mạng, bản kiểm kê các tính năng được hỗ trợ bởi từng thiết bị mạng, thống
kê mạng, theo dõi máy chủ lưu trữ thông tin và thông tin gói. Các ứng dụng
có thể đưa ra quyết định tương ứng, sau đó lớp điều khiển chuyển các quyết
định đó thành các hướng dẫn được tải xuống lớp cơ sở hạ tầng và thực thi
các cài đặt mạng thích hợp cho lưu lượng hiện tại.
Lớp điều khiển được hình thành là tập trung về mặt logic, có nghĩa là
NOS có thể hoạt động dưới một cụm máy chủ vật lý để chia sẻ khối lượng
công việc của hệ thống.
Lớp cơ sở hạ tầng (Infrastructure layer)
Lớp cơ sở hạ tầng bao gồm thành phần dữ liệu của kiến trúc SDN, được
đại diện bởi các thiết bị chuyển tiếp như bộ chuyển mạch và bộ định tuyến.
Chúng chuyển tiếp các gói theo các hướng dẫn mà lớp điều khiển nhận được,
như loại bỏ một gói hoặc gửi gói tin đó ra ngoài thông qua một giao diện đầu
ra. Các thiết bị chuyển tiếp duy trì liên lạc với lớp điều khiển để giữ cho hệ
thống được cập nhật về trạng thái mạng của chúng như các cổng đang hoạt
động, hàng xóm liền kề, các tính năng được hỗ trợ, thông tin bộ đếm và thông
báo sự kiện.
Về mặt logic, các thiết bị chuyển tiếp được xem như một Datapath và
được xác định bởi một Datapath ID (DPID). Thông tin này được bộ điều
khiển SDN sử dụng để giải quyết các hướng dẫn cụ thể cho các thiết bị nhất
định, như các hành động chuyển tiếp hoặc để xác định từng thiết bị mạng
trong phần trừu tượng cấu trúc liên kết.
16/60
Kênh giao tiếp giữa lớp cơ sở hạ tầng và lớp điều khiển được gọi là
Giao diện hướng Nam, được đặc trưng bởi một số giao thức truyền thông
thực hiện tương tác giữa bộ điều khiển SDN và các đường dẫn dữ liệu. Giao
thức SouthBound phổ biến nhất được sử dụng là OpenFlow, được hầu hết
các nhà cung cấp chấp nhận vì OpenFlow được phát triển liên tục để hoạt
động cho việc điều khiển mạng và truyền thông SouthBound.
Software Defined Wireless Networking
Trong các mạng SDN, một điều khiển tập trung thường được sử dụng
để cung cấp cái nhìn toàn cầu về mạng và đơn giản hóa hoạt động mạng cũng
như mạng khả năng lập trình. Tuy nhiên, trong mô hình tập trung, việc kiểm
soát đường dẫn giữa các thiết bị mạng và bộ điều khiển có thể là điểm thất
bại duy nhất hoặc điểm nghẽn tiềm ẩn. Do đó, SDN controller truyền thống
đã được mở rộng và sau đó được nhúng vào mọi nút, nhằm mục đích giảm
nguy cơ mất kết nối với bộ điều khiển và sự chậm trễ trong quá trình truyền
lệnh từ bộ điều khiển đến các thiết bị. Mô hình này cũng cho phép sử dụng
lợi ích của SDN trong môi trường không dây.Ví dụ: khả năng phục hồi của
hệ thống đã được cải thiện bởi chuyển một kết nối đang diễn ra từ giao diện
vật lý sang một cái khác. Hiệu suất của hệ thống được đánh giá trong một
thử nghiệm thực tế và kết quả thử nghiệm cho thấy hệ thống được trang bị
local SDN controller là giải pháp đầy hứa hẹn để chuyển giao trong mạng
không dây. [3]
SDN CONTROLLER
SDN controller truyền thống
Kiến trúc SDN bao gồm ba lớp như được hiển thị trong (Hình 2.2). Lớp
thấp nhất là Mặt phẳng dữ liệu bao gồm chuyển tiếp các thiết bị mạng, tức
là các thiết bị chuyển mạch, để đáp ứng vớichuyển tiếp dữ liệu và thu thập
số liệu thống kê. Các công tắc là thường được sản xuất bởi các công ty khác
nhau và được trang bị hệ thống hoạt động tư nhân của họ. Do đó, mạng quản
trị viên phải tuân theo hướng dẫn của công ty để định cấu hình công tắc để
chỉ cần chuyển lưu lượng từ các cổng đầu vào sang các cổng ra. Ngược lại,
trong mạng SDN, bộ chuyển mạch thực hiện chuyển tiếp các gói dựa trên
các quy tắc luồng được lưu giữ trong cơ sở dữ liệu hoặc bảng luồng. Quy tắc
luồng hoặc mục nhập luồng là được lắp vào, sửa đổi hoặc loại bỏ bởi mặt
phẳng điều khiển thông qua một kênh giao tiếp được gọi là giao diện hướng
17/60
Nam (SBI). Giao diện thường sử dụng một giao thức có tên OpenFlow cho
giao tiếp giữa Mặt phẳng dữ liệu và Mặt phẳng điều khiển. Các công tắc hỗ
trợ OpenFlow thường yêu cầu bộ điều khiển với PACKET_IN thông báo khi
họ không tìm thấy kết quả phù hợp quy tắc luồng cho các gói đến. Người
điều khiển sau đó trả lời bằng cách yêu cầu bộ chuyển mạch gán các hành
động cho các gói. Đối với ví dụ, bộ điều khiển trả lời bằng một thông báo
FLOWMOD, là một trong những thông báo chính, để sửa đổi trạng thái của
công tắc điện
Hình 2.2 Kiến trúc SDN
Trên mặt phẳng Điều khiển, bộ điều khiển không chỉ chịu trách nhiệm
để kiểm soát hoạt động mạng, nhưng cũng lắng nghe yêu cầu từ các ứng
dụng trong Mặt phẳng ứng dụng. Các bộ điều khiển giải thích yêu cầu của
ứng dụng và vượt qua các hàng đợi tương ứng với mặt phẳng dữ liệu. Mặt
phẳng điều khiển cũng cung cấp các dịch vụ mạng như chính sách quản lý
hoặc chất lượng của dịch vụ cho các ứng dụng. Bộ điều khiển giao tiếp với
các ứng dụng thông qua giao diện ứng dụng - bộ điều khiển hoặc giao diện
hướng Bắc (NBI). Đặc tả SDN không chuẩn hóa NBI. SDN cho phép phần
mềm điều khiển tự cung cấp phương pháp nói chuyện với các ứng dụng.
Local SDN Controller
Thông thường, SDN controller tập trung chỉ cần giao tiếp với công tắc
OpenFlow và xử lý mạng sự kiện do họ hỏi vì SDN controller có chế độ xem
toàn cầu của mạng. Tuy nhiên, khi bộ điều khiển và công tắc OpenFlow được
18/60
triển khai trên cùng một nút, bộ điều khiển không biết gì về cấu trúc liên kết
của toàn bộ mạng. Thay vào đó, local SDN controller có thông tin mạng cục
bộ (tức là yêu cầu ARP hoặc RSSI) không được công tắc xử lý. Qua đó, trong
công việc này, một Local SDN Controller đã được phát triển để cho phép
Controller xử lý các yêu cầu chuyển đổi cũng như hành vi mạng cục bộ.
Logic điều khiển của nút di động dựa trên SDN, trong đó SDN
Controller truyền thống và một Local SDN controller được nhúng.
Hình 2.3. Logic điều khiển nút di động dựa trên SDN
Nút có thể là máy tính bảng, điện thoại di động hoặc máy tính xách tay.
Ở trên cùng, bộ điều khiển ban đầu và phần mở rộng chúng đang kiểm soát
hành vi mạng cục bộ cho nút. Các bộ SDN Controller truyền thống thông
qua giao thức OpenFlow (ví dụ Open vSwitch – OVS). Ở bên phải, Local
SDN controller thu thập trực tiếp thông tin mạng từ các giao diện mạng vật
lý. Local SDN controller là được phát triển để có thể tùy chỉnh cấu hình mạng
của bất kỳ giao diện nào. Thông tin thu thập được lưu trữ trong cơ sở dữ liệu
để SDN controller truyền thống có thể đọc và rõ hơn về cấu trúc liên kết
mạng. Ở giữa, OVS điều hướng lưu lượng mạng vào và ra khỏi nút. Local
SDN controller cung cấp một hoặc nhiều cầu ảo hoạt động như một hoặc
nhiều điểm trung gian giao diện nằm giữa giao diện vật lý và các ứng dụng.
Ở phía dưới, tất cả các giao diện mạng vật lý đều được cấu hình để trở thành
19/60
các cổng chuyển đổi của OVS. Một cây cầu có thể bao gồm một hoặc nhiều
giao diện vật lý nhưng giao diện không thể thuộc về đến nhiều hơn một cây
cầu.
Yêu cầu thiết kế:
a) Local SDN controller phải hoạt động với mọi SDN controller hiện
có:
Mặc dù SDN Controller hiện tại có thiết kế riêngvới các API khác nhau,
Local SDN controller phải có thể hoạt động với họ trong mạng SDN. Local
SDN controller, không có kênh giao tiếp ngoại trừ kênh có công tắc, có thể
đọc thông tin mạng bất cứ lúc nào. Nếu thu thập thông tin đủ lớn, SDN
Controller có thể có đủ kiến thức về cấu trúc liên kết mạng. Điều đó là có
thể vì local controller có thể trao đổi và cập nhật cơ sở dữ liệu đến bất kỳ
nút nào mà local controller kết nối.
Attributes
Tag name
Name Switch port IP MAC Status ID Key
Connection X X
Media X X X
Bridge X X X X X
Interface X X X X X
Bảng 1: Bảng dữ liệu trạng thái mạng
Bảng 1, cho thấynội dung chính của tệp, trong đó, tất cả các cấu hình
mạng được mô tả. Ví dụ:
Thẻ Connection: là để trình bày tên nút và trạng thái kết nối từ nút cục
bộ đến các nút khác. Thẻ Connection có hai thuộc tính tên là Tên và Trạng
thái được đánh dấu bằng X.
Thẻ Media: hiển thị phương thức mà nút cục bộ đang sử dụng để kết
nối với bên ngoài. Thẻ Media có ba thuộc tính Name, ID và Key. Thuộc tính
Name hiển thị tên của kết nối, nghĩa là Wi-Fi hoặc Bluetooth, trong khi ID
hiển thị SSID của AP hoặc địa chỉ MAC của Bluetooth master và Key chứa
chuỗi bảo mật để xác thực.
20/60