ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
Lê Đắc Nhường
NGHIÊN CỨU MỘT SỐ THUẬT TOÁN NÂNG CAO CHẤT LƯỢNG DỊCH VỤ TRONG MẠNG THẾ HỆ MỚI
Chuyên ngành: Cơ sở toán học cho Tin học Mã số: 62.46.01.10
DỰ THẢO TÓM TẮT LUẬN ÁN TIẾN SỸ TOÁN HỌC
Hà Nội - 2014
Công trình được hoàn thành tại: Khoa Toán - Cơ - Tin học, Trường Đại học
Khoa học Tự nhiên, Đại học Quốc gia Hà Nội.
Người hướng dẫn khoa học :
PGS.TS Lê Trọng Vĩnh
PGS.TS Ngô Hồng Sơn
Phản biện: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . .
Phản biện: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . .
Phản biện: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . .
Luận án sẽ được bảo vệ trước Hội đồng cấp Đại học Quốc gia chấm luận án
tiến sĩ họp tại . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vào hồi giờ ngày tháng năm 20...
Có thể tìm hiểu luận án tại:
- Thư viện Quốc gia Việt Nam - Trung tâm Thông tin - Thư viện, Đại học Quốc gia Hà Nội
Mục lục
Mở đầu
1
1 Tổng quan về QoS trong NGN
3 3 3 3 3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Mạng thế hệ mới 1.2 Chất lượng dịch vụ . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Bài toán tối ưu tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Thuật toán tối ưu đàn kiến . . . . . . . . . . . . . . . . . . . . . .
2 Cấp phát tài nguyên cho các dịch vụ
2.1 Mở rộng dung lượng mạng không dây . . . . . . . . . . . . . . . . . 2.1.1 Mô hình bài toán . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Đề xuất thuật toán ACO-MRDL tối ưu mở rộng dung lượng 2.1.3 Kết quả thực nghiệm và đánh giá . . . . . . . . . . . . . . . 2.2 Định vị tài nguyên cho các lớp dịch vụ . . . . . . . . . . . . . . . . 2.2.1 Mô hình bài toán . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Tối ưu định vị tài nguyên tập trung cho các lớp dịch vụ . . . 2.2.2.1 Đề xuất thuật toán ACO-ĐVTN . . . . . . . . . . 2.2.2.2 Đề xuất thuật toán MMAS-ĐVTN . . . . . . . . .
4 4 4 5 6 8 8 9 9 9 2.2.3 Kết quả thực nghiệm và đánh giá . . . . . . . . . . . . . . . 10 2.3 Đáp ứng tài nguyên cho các luồng đa phương tiện . . . . . . . . . . 13 2.3.1 Mô hình bài toán . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3.2 Đề xuất thuật toán MMAS tối ưu QoS luồng đa phương tiện 14 2.3.3 Kết quả thực nghiệm và đánh giá . . . . . . . . . . . . . . . 15 2.4 Kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 An ninh dịch vụ trong mạng NGN
19 3.1 Kiến trúc đảm bảo ninh trong mạng NGN . . . . . . . . . . . . . . 19 3.2 Tấn công từ chối dịch vụ . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3 Đề xuất giải pháp phòng chống dựa trên chính sách . . . . . . . . . 19 3.4 Kết luận chương 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Kết luận
24
Danh mục các công trình khoa học
i
Mở đầu
Mạng thế hệ mới (Next Generation Network-NGN ) [12] là sự hội tụ và kế thừa cả 3 mạng: thoại (PSTN), không dây và Internet hiện nay thành một cơ sở hạ tầng chung thống nhất theo nguyên tắc cung cấp đa dịch vụ trên công nghệ chuyển mạch gán nhãn đa giao thức MPLS/IP(MultiProtocol Lable Switching/Internet Protocol ) đang là xu hướng phát triển mới của ngành viễn thông thế giới và của cả Việt Nam. Mục tiêu NGN hướng đến là cung cấp các dịch vụ đa phương tiện chất lượng cao theo yêu cầu người dùng trên nền IP. Đây là một vấn đề mới đang thu hút được các nhà khoa học, trường đại học, viện nghiên cứu, nhà cung cấp dịch vụ quan tâm nghiên cứu và triển khai.
Chất lượng dịch vụ (QoS) [13] là thước đo đánh giá khả năng và chất lượng của các dịch vụ được cung cấp được nhìn nhận từ 2 khía cạnh người sử dụng và nhà cung cấp dịch vụ mạng. Với nhà cung cấp, QoS liên quan chặt chẽ đến hiệu năng mạng, còn với người dùng QoS được đánh giá dựa trên chất lượng trải nghiệm (Quality of Experiences-QoE) [8]. Vấn đề QoS trong mạng đã được quan tâm từ những năm 1980 và phát triển mạnh cho đến ngày nay nhằm đảm bảo chất lượng của các ứng dụng thời gian thực. Việc đáp ứng QoS theo yêu cầu trên cần có cơ sở hạ tầng tốt và qui trình cấp phát, quản lý tài nguyên mạng hiệu quả. Bởi vì QoS phụ thuộc vào sự kết hợp của nhiều yếu tố như thành phần mạng, cơ chế xử lý và điều khiển trong mạng. Đối với mỗi phần có các yêu cầu về QoS tương ứng liên quan tới việc ứng dụng các chuẩn thiết kế, lựa chọn các giao thức phù hợp, xác định cấu trúc mạng, các phương pháp nhận dạng, lựa chọn công nghệ xây dựng mạng, thiết kế quản lý nút bộ đệm, xem xét để đảm bảo rằng các tham số chất lượng như: sự tắc nghẽn, độ sẵn sàng, trễ, biến đổi trễ, thông lượng, độ suy hao, sự tin cậy,. . . không vượt quá khoảng thời gian dịch vụ được đáp ứng và lưu lượng tải giữa hai điểm bất kì đã chọn trong mạng [24]. Như vậy, chúng ta có thể nhận thấy sự liên quan chặt chẽ giữa QoS và hiệu năng mạng, rõ ràng khi nhìn vào các chỉ số của QoS ta có thể đánh giá được năng lực của mạng và ngược lại khi tham khảo các yếu tố của hiệu năng mạng, ta có thể đưa ra về mức QoS cho các dịch vụ được cung cấp [13, 21].
Các công trình nghiên cứu về đảm bảo QoS trong NGN trong và ngoài nước rất đa dạng với nhiều cách tiếp cận khác nhau. Trong phạm vi nghiên cứu, luận án chỉ tập trung đến hai vấn đề chính đang thu hút được nhiều sự quan tâm là: Qui hoạch, chia sẻ, nâng cấp và mở rộng cơ sở hạ tầng mạng. Vì vây, mục tiêu của luận án “Nghiên cứu một số thuật toán nâng cao chất lượng dịch vụ trong mạng thế hệ mới ” hướng đến là tập trung đề xuất các thuật toán định vị, mở rộng dung lượng, quản lý cấp phát tài nguyên hiệu quả đáp ứng được các yêu cầu đa dạng của người dùng về QoS dựa trên tiếp cận Meta-Heuristic sử dụng thuật toán tối ưu đàn kiến. Cụ thể, luận án tập trung nghiên cứu và đề xuất thuật toán tối ưu đàn kiến giải quyết các bài toán sau:
1
(cid:4) Mở dung lượng mạng không dây kế thừa cơ sở hạ tầng đảm bảo nhu cầu về
lưu lượng trên toàn hệ thống.
(cid:4) Định vị tài nguyên tập trung đáp ứng QoS cho các lớp dịch vụ theo mô hình
phân bố tối ưu tài nguyên dựa vào độ đo.
(cid:4) Đáp ứng tài nguyên cho các luồng đa phương tiện đảm bảo QoS cho các dịch vụ thời gian thực dựa trên mô hình dịch vụ tích hợp theo hướng dành trước tài nguyên.
(cid:4) Đề xuất giải pháp phòng chống tấn công từ chối dịch vụ trong mạng NGN
dựa trên chính sách an ninh bảo mật riêng.
Với các mục tiêu của luận án như trên, luận án được tổ chức thành 3 chương
như sau:
(cid:4) Chương 1 giới thiệu một số kiến thức cơ sở, phân tích vấn đề đảm bảo chất lượng dịch vụ trong mạng NGN và lý do lựa chọn hướng tiếp cận dựa trên thuật toán ACO để giải quyết các bài toán.
(cid:4) Chương 2, luận án đề xuất thuật toán ACO tối ưu mở dung lượng mạng không dây kế thừa cơ sở hạ tầng sẵn có với mục tiêu hướng đến là tối thiểu chi phí vận hành, chi phí cài đặt, chi phí nâng cấp và chi phí xây mới các thành phần mạng để đảm bảo nhu cầu về lưu lượng trên toàn hệ thống. Tiếp đó, tác giả đề xuất thuật toán MMAS tối ưu định vị tài nguyên tập trung đáp ứng QoS cho các lớp dịch vụ theo mô hình phân lớp dịch vụ theo hướng phân lớp lưu lượng, tối ưu các luồng đa phương tiện đảm bảo QoS cho các dịch vụ thời gian thực dựa trên mô hình dịch vụ tích hợp theo hướng dành trước tài nguyên.
(cid:4) Chương 3, luận án tập trung luận án phân tích những thách thức và khó khăn trong việc đảm bảo an ninh các dịch vụ trong mạng NGN đề xuất giải pháp phòng chống tấn công từ chối dịch vụ dựa trên chính sách an ninh riêng được thiết lập trên các nút Router.
Cuối cùng là kết luận và hướng phát triển.
Những kết quả nghiên cứu và đóng góp của luận án có ý nghĩa trong việc bổ sung và hoàn thiện các giải pháp tối ưu định vị các trạm điều khiển, mở rộng dung lượng mạng, cấp phát tài nguyên cho các lớp, luồng dịch vụ đảm bảo yêu cầu về QoS trong mạng có thể thực thi trong thời gian tuyến tính với chất lượng lời giải tốt hơn các tiếp cận trước đó. Ưu điểm của các thuật toán đề xuất là sự hội tụ nhanh với các quy tắc heuristic kết hợp học tăng cường thông qua thông tin vết mùi cho phép từng bước thu hẹp miền tìm kiếm, mà vẫn không loại bỏ các lời giải tốt để nâng cao chất lượng lời giải. Các kết quả của luận án đã được công bố trong 4 báo cáo tại các Hội nghị quốc tế, 3 bài báo trên các tạp chí quốc tế, 2 bài báo trong Kỷ yếu Hội thảo Quốc gia.
2
Chương 1
Tổng quan về QoS trong NGN
1.1 Mạng thế hệ mới
Mạng thế hệ mới (Next Generation Network -NGN) là mạng đa dịch vụ dựa trên nền IP cho phép đáp ứng các dịch vụ cá nhân, quản lý thông tin hiệu quả, dễ dàng mở rộng dung lượng, phát triển các dịch vụ mới theo thời gian thực và đa phương tiện, đảm bảo độ tin cậy, thuận tiện cũng như dễ dàng sử dụng [12].
1.2 Chất lượng dịch vụ
Chất lượng dịch vụ (Quality of Service-QoS) [24] là một khái niệm rộng được tiếp cận theo nhiều hướng khác nhau. Theo ITU-T: QoS là tập hợp các khía cạch của hiệu năng dịch vụ nhằm xác định cấp độ thỏa mãn của người sử dụng đối với dịch vụ [13]. Còn IETF nhìn nhận: QoS là khả năng phân biệt luồng lưu lượng để mạng có các ứng xử phân biệt đối với các kiểu luồng lưu lượng, QoS bao gồm cả việc phân loại các dịch vụ và hiệu năng tổng thể của mạng cho mỗi loại dịch vụ [1].
1.3 Bài toán tối ưu tổ hợp
1.4 Thuật toán tối ưu đàn kiến
Thuật toán tối ưu đàn kiến (Ant Colony Optimization-ACO) [7] đầu tiên là Hệ kiến (Ant System-AS ) [7] do M. Dorigo đề xuất năm 1991 giải bài toán TSP. Sau đó, có nhiều biến thể được nghiên cứu tập trung vào nâng cao hiệu năng tính toán dựa trên lựa chọn các đặc trưng trong thủ tục Xây dựng các phương án và Cập nhật vết mùi. Quá trình phát triển các thuật toán ACO được có thể xem trong [20, 22, 27, 29]. Tuy nhiên, thuật toán thông dụng nhất là MMAS và ACS.
Cơ sở sự hội tụ của thuật toán: Năm 2000, W.J Gutjahz chứng minh được tính hội tụ của thuật toán MMAS trong một số điều kiện nhất định MMAS hội tụ tới một lời giải tối ưu với độ chính xác tùy ý nhưng chưa xét đến yếu tố có sử dụng thông tin heuristic [11]. Năm 2002, M. Dorigo và T. St¨utzle đã chứng minh được tính hội tụ của thuật toán MMAS và ASC [28] rằng: ∀ (cid:15) > 0, ∃ t đủ lớn P (t) > 1−(cid:15) P (t) = 1. Năm 2008, Plelegrini và Elloro chỉ ra rằng sau một thời gian do đó lim t→∞
chạy, đa số vết mùi trên cạnh trở nên bé và chỉ có số ít cạnh có giá trị vết mùi là lớn vượt trội trong [26]. Đây là cơ sở lý thuyết vững vàng và mở ra một loạt các nghiên cứu đầy hứa hẹn về các tham số điều khiển trong ACO.
3
Chương 2
Cấp phát tài nguyên cho các dịch vụ
2.1 Mở rộng dung lượng mạng không dây
2.1.1 Mô hình bài toán
Trong [3], Basole cùng các cộng sự đã mô hình hóa bài toán mở rộng dung lượng mạng không dây (MRDL) với kiến trúc gồm m MS, n BTS và p BSC. Bài toán gồm 2 giai đoạn: giai đoạn đầu là khởi tạo các kết nối từ MS đến BTS và các kết nối của BTS đến BSC và giai đoạn thứ hai là mở rộng năng lực mạng và tăng lưu lượng truy cập.
Định nghĩa 2.1 (Bài toán mở rộng dung lượng mạng không dây-MRDL [3]).
(cid:88)
(cid:88)
Min
cost intallk (Wk −δk )
cost connectjt k (Yjt k −βjt k )+
n (cid:88) p (cid:88)
(cid:88)
(cid:88)
(cid:88)
(cid:88)
+
MaxBTS capjt (Zjt −αjt )) +
cost upgradej (
cost setupjt Zjt
j =1 k =1 k ∈P2 t∈Tj
(2.1)
Thoả mãn các ràng buộc:
j ∈N2 j ∈N1 t∈Tj t∈Tj
(cid:88)
(2.2)
Xijt = 1, ∀ i = 1..m
n (cid:88)
(2.3)
dij Xijt
(cid:54) MaxCovjt Zjt , ∀ i = 1..m, j = 1..n, t ∈ Tj (cid:88) (cid:54) 1, ∀ j = 1..n
(2.4)
Zjt
j =1 t∈Tj
t∈Tj
(cid:54)
(2.5)
Zjt
Yjt k , ∀ j = 1..n, t ∈ Tj
p (cid:88)
(2.6)
Yjt k (cid:54) Wk , ∀ k = 1..p, j = 1..n, t ∈ Tj
k =1
D s
(2.7)
t ∈ Tj
(cid:54) MaxBTS Capjt ×Zjt , ∀ j = 1..n,
m (cid:88) 2 (cid:88) i Xijt s=1 i=1
(cid:88)
(2.8)
Yjt k (cid:54) MaxBSC Capk ×Wk , ∀ k = 1..p
n (cid:88)
(2.9)
Xijt ∈ {0, 1} , Yjt k ∈ {0, 1} , Zjt ∈ {0, 1} , Wk ∈ {0, 1} ∀ i = 1..m, j = 1..n, k = 1..p, t ∈ Tj
4
j =1 t∈Tj
Bài toán mở rộng dung lượng mạng không dây là bài toán tối ưu đa mục tiêu. Đây là một bài toán khó, có rất nhiều định nghĩa khác nhau đề cập đến phương án tối ưu như: Pareto, Borwein, Benson, Geoffrion, Kuhn-Tucker,. . . nhưng chưa có thuật toán hiệu quả với thời gian đa thức [3, 25]. Trong [19], chúng tôi đã đề xuất thuật toán GA để giải mở rộng dung lượng mạng không dây dựa trên việc kết hợp hai quần thể.
2.1.2 Đề xuất thuật toán ACO-MRDL tối ưu mở rộng dung lượng
Đầu tiên, ta xây dựng đồ thị G1 = (V1, E1) với V1 = {M ∪N 1∪P 1} là tập các MS, BTS và BSC, E1 là tập các kết nối giữa MSi đến BTSj và kết nối giữa BTSj đến BSCk đã có thỏa mãn các ràng buộc của bài toán. Để tìm luồng cực đại trên đồ thị G1, ta thêm 2 đỉnh nguồn S và đỉnh đích D như Hình 2.1 với các biến chỉ định. Trọng số của các cạnh trên đồ thị G1 được xác định như sau: c(S , MSi ) = D s i , (i = i , (i = 1..m, j = 1..n1), c(j , k ) = (cid:80) D s 1..m), c(i, j ) = D s i , (j = 1.n1, k = 1..p1), c(k , D) = (cid:80) c(i, j ), (j = 1..n1, k = 1..p1). Tiếp theo, ta xây dựng đồ thị đầy đủ G2 = (V2, E2) với V2 = {M ∪N ∪P } là tập hợp tất cả các MS, BTS, BSC sẵn có và tiềm năng, E2 là tập cạnh chứa tất cả kết nối giữa MSi đến BTSj , giữa BTSj đến BSCk thỏa mãn các ràng buộc từ (2.2)-(2.9). Trong đó, các nút tô màu đậm là tập các BTS và BSC tiềm năng. Phương án của bài toán sẽ ứng với các đường đi của các con kiến nhân tạo trên đồ thị G2. Mỗi con kiến được mã hóa bởi vectơ Antk = {x1, x2, ...xm+n+p} với qui ước: xi = 1 nếu i ∈ [1..m] thì MSi được sử dụng, nếu i ∈ [m+1..m+n] thì sử dụng BTSj (j = i−m), nếu i ∈ [m+n+1..m+n+p] thì sử dụng BSCk (k = i−m−n) và ngược lại.
Hình 2.1 – Đồ thị đầy đủ với các biến quyết định
Ma trận mùi τij được mã hóa gồm các số thực được sinh ra từ đồ thị G2 dể biểu diễn vị trí di chuyển của các con kiến. Đường đi của mỗi con kiến Antk thể hiện việc cập nhật vết mùi trên các cạnh. Mỗi cạnh của đồ thị G2 sẽ mô tả mức độ mùi được lưu lại, tại mỗi nút con kiến Antk sẽ quyết định nút tiếp theo trong đường đi dựa vào vị trí hiện thời tại nút i và xác suất lựa chọn nút tiếp theo để di chuyển được xác định bởi (??). Thông tin heuristic ηij mô tả khả năng lựa chọn nút j được tính toán phụ thuộc vào hàm mục tiêu của bài toán ηij = 1 với dij là dij khoảng cách kết nối từ MSi đến BTSj khi kiến ở nút i (hoặc từ BTSi đến BSCj ). Sau mỗi vòng lặp, vết mùi trên mỗi cạnh được cập nhật lại theo công thức (??)
5
2.1.3 Kết quả thực nghiệm và đánh giá
Bộ dữ liệu thực nghiệm gồm vị trí các trạm MS, BTS và BSC được sinh ra ngẫu nhiên trên kích thước lưới xác định với số lượng và kiểu các trạm BTS và BSC được thiết lập thông trong Bảng 2.1. Dữ liệu được sinh ngẫu nhiên theo phân phối đều thỏa mãn các điều kiện sau: D s i ∈ [1..10], MaxBTS Capjt ∈ [50..100], MaxBSC Capk ∈ [200..500], MaxBTS Covj ∈ [25..100], cost connectjtk, cost installk, cost upgradej, cost setupjt trong phạm vi [1..50]. Tọa độ các MS, BTS, BSC lần lượt là (MSi1, MSi2), (BTSj 1, BTSj 2) và (BSCk 1, BSCk 2) được phân bố đều trên lưới. Các thuật toán được khai báo và cài đặt trên ngôn ngữ C với tham số thực nghiệm của ACO-MRDL là: K = 100,Nmax = 500, α = 1, β = 10, ρ = 0.5, nk = 30.
Bảng 2.1 – Thông tin về bộ dữ liệu thực nghiệm mở rộng dung lượng mạng
j = 1/(cid:0)cost connectij + cost intallj +cost upgradej + c ost setupj (cid:1) là lượng với ∆τ k vết mùi kiến k để lại khi đi từ nút i đến nút j . Khi đó, sự thích nghi của kiến k được tính theo công thức (2.1). Độ phức tạp của thuật toán ACO-MRDL là: O(M ×N ×P +NMax ×K ×M ×N ×P ) hay O(NMax ×K ×M ×N ×P ) với NMax là số vòng lặp tối đa, K là số lượng kiến.
Số trạm MS Số trạm BTS Số trạm BSC
Bộ Test Số kiểu P Số kiểu Kích thước lưới M N N1 N2 P1 P2
Thực nghiệm 1: Để đánh giá hiệu quả của thuật toán đề xuất, luận án lựa chọn tiêu chí so sánh là khả năng mở rộng dung lượng kết nối trong mạng, chi phí mở rộng và thời gian thực thi giữa 2 thuật toán. Với các tham số được thiết lập, chúng tôi đã thực thi các thuật toán GA-MRDL và ACO-MRDL 50 lần và so sánh khả năng mở rộng dung lượng mạng giữa các thuật toán dựa trên dung lượng mạng đạt được trong trường hợp tốt nhất và trung bình trong Bảng 2.2. Các giá trị in đậm thể hiện khả năng mở rộng tốt nhất trong mỗi trường hợp. Cột cuối đánh giá khả năng mở rộng trung bình của mỗi thuật toán so với dung lượng mạng ban đầu được khởi tạo với các trạm sẵn có ∆Mở rộng.
Bảng 2.3 so sánh giá trị hàm mục tiêu đạt được trong trường hợp tốt nhất, trung bình và tồi nhất giữa các thuật toán. Kết quả trung bình phản ánh chất lượng của thuật toán, còn các kết quả tốt nhất và tồi nhất để tham khảo về tính khám phá còn độ lệch chuẩn để tham khảo tính ổn định của thuật toán so với kết quả tốt nhất.
Đối chiếu kết quả giữa Bảng 2.2 và Bảng 2.3 ta thấy mối quan hệ giữa khả năng mở rộng dung lượng với hàm mục tiêu tối thiểu chi phí. Điều dễ thấy là chi phí tối ưu gần như đồng nghĩ với khả năng mở rộng tối ưu vì chi phí được xây
6
10 30 100 250 500 1000 2500 5000 7500 10000 4 6 10 25 50 150 350 550 750 950 3 3 6 15 30 90 200 350 450 650 1 3 4 10 20 60 150 200 300 300 2 2 2 10 10 30 40 100 150 200 1 2 3 5 10 20 60 50 50 100 3 4 5 15 20 50 100 150 200 300 1 3 3 5 6 8 10 15 20 30 1 3 4 5 8 10 20 30 40 50 [150×150] [150×150] [150×150] [500×500] [500×500] [500×500] [500×500] [1000×1000] [1000×1000] [1000×1000] #1 #2 #3 #4 #5 #6 #7 #8 #9 #10
Bảng 2.2 – So sánh dung lượng được mở rộng của GA-MRDL và ACO-MRDL
GA-MRDL ACO-MRDL Bộ Test Khởi tạo Tốt nhất Trung bình Mở rộng Tốt nhất Trung bình Mở rộng ∆Mở rộng
Bảng 2.3 – So sánh hàm mục tiêu của thuật toán GA-MRDL và ACO-MRDL
#1 #2 #3 #4 #5 #6 #7 #8 #9 #10 41.18 89.29 184.98 247.15 562.16 984.34 1585.58 3102.62 4851.82 6205.04 76.39 109.74 227.18 298.22 793.34 1120.47 1896.41 3965.89 5671.74 8326.06 75.12 107.37 237.22 295.87 792.58 1115.28 1886.51 3936.72 5621.14 8303.92 33.94 18.08 42.24 48.72 230.42 130.94 300.93 834.10 769.32 2098.88 125.59 121.14 219.08 378.32 909.84 1174.77 1946.81 4119.09 5962.34 8920.46 124.23 116.95 218.16 374.73 904.17 1154.98 1942.55 4110.93 5945.21 8914.09 83.05 27.66 33.18 127.58 342.01 170.64 356.97 1008.31 1093.39 2709.05 49.10 9.59 -9.05 78.87 111.58 39.70 56.04 174.21 324.08 610.17
GA-MRDL ACO-MRDL
dựng dựa trên khả năng phân bố dung lượng. Khi dung lượng tối ưu theo yêu cầu thì chi phí cũng sẽ giảm tối thiểu. Để kiểm chứng lại độ phức tạp tính toán và hiệu suất thực thi giữa các thuật toán, thời gian thực hiện trung bình được thống kê và so sánh trong Hình 2.2.
Hình 2.2 – So sánh thời gian thi trung bình của GA-MRDL và ACO-MRDL
Thời gian thực thi của thuật toán ACO-MRDL nhanh hơn so với GA-MRDL. Sự khác biệt này càng rõ khi số lượng các giải pháp lựa chọn tăng lên ứng với số lượng các trạm tiềm năng lớn trong các bài toán lớn. Điều đó một lần nữa khẳng định được ưu điểm của cấu trúc đồ thị biểu diễn không gian trạng thái so với việc sử dụng các phép toán lai ghép và đột biết trên quần thể.
Thực nghiệm 2: Để đánh giá tác động của số kiến đến độ hội tụ và thời gian thực thi của thuật toán. Chúng tôi tiến hành thực nghiệm bằng cách thay đổi lượng kiến từ 20 đến 250 và giữ nguyên số vòng lặp NMax = 500 với bài toán #2. Sự ảnh hưởng của số kiến đến thời gian tìm được lời giải tối ưu của bài toán được thể hiện qua Hình 2.3(a). Dữ liệu trên biểu đồ chứng tỏ rằng nếu ta tăng số
7
Bộ Test Tốt nhất Trung bình Tồi nhất Độ lệch Tốt nhất Trung bình Tồi nhất Độ lệch 1.84% 1.69% 1.25% 1.14% 1.07% 0.98% 0.84% 0.46% 0.13% 0.06% 110.66 2.59% 192.48 3.11% 277.63 2.53% 319.51 2.52% 5.09% 852.27 1.69% 1124.43 1.55% 2264.49 1.49% 3532.55 0.86% 5841.74 0.36% 7159.05 116.12 192.48 277.63 319.51 873.67 1136.37 2264.49 3570.63 5854.76 7163.12 112.69 195.73 281.11 323.14 861.35 1135.49 2283.58 3548.63 5849.16 7163.13 113.52 198.47 284.64 327.54 895.69 1143.42 2299.57 3585.26 5891.84 7185.17 119.13 203.62 295.93 332.77 925.36 1149.42 2312.50 3594.26 5892.86 7196.26 117.26 197.87 289.42 328.57 873.94 1143.17 2295.13 3559.85 5867.21 7165.72 #1 #2 #3 #4 #5 #6 #7 #8 #9 #10
lượng kiến lên thì thời gian thực thi sẽ tăng theo, nhưng nếu giảm số lượng kiến quá ít thì lại làm tăng thời gian thực hiện bởi số lượng giải pháp được xem xét quá ít dẫn đến phải thực hiện nhiều lần.
Hình 2.3 – Ảnh hưởng của số kiến và số vòng lặp đến thời gian thực thi
Thực nghiệm 3: Để đánh giá tác động của các tham số vòng lặp tới giá trị của hàm mục tiêu, tôi tiến hành thực nghiệm bằng cách thay đổi số vòng lặp NMax từ 25, 50, đến 500 trong khi giữ nguyên số lượng kiến là 50 với bài toán #2. Kết quả thực nghiệm thể hiện mối quan hệ giữa số vòng lặp đến hàm mục tiêu của thuật toán được cho trong Hình 2.3(b). Thực nghiệm 3 chỉ ra rằng số lượng vòng lặp ảnh hưởng rất lớn đến phương án bởi số lượng vòng lặp càng lớn thì hàm mục tiêu càng hội tụ. Do đó, việc lựa chọn tham số vòng lặp là bao nhiêu cũng rất quan trọng.
2.2 Định vị tài nguyên cho các lớp dịch vụ
2.2.1 Mô hình bài toán
Bài toán cấp phát tài nguyên cho các lớp dịch vụ thỏa mãn ràng buộc trễ
xác suất trên từng lớp [14] theo MBORA được định nghĩa như sau:
Định nghĩa 2.2 (Cấp phát tài nguyên cho các lớp dịch vụ theo yêu cầu QoS [14]).
(cid:41)
(cid:40) N
(cid:88)
(2.10)
f = max
di Di (si ) e βi (Di (si )−di )
pi si C −
N (cid:88)
thỏa mãn ràng buộc:
(2.11)
si (cid:54) 1
si (cid:62) 0, ∀ i = 1..N N (cid:80) i=1 si > ¯αi , ∀ i = 1..N
Trong đó, lợi nhuận được xác định thông qua hàm tuyến tính giữa mức giá pi và loại dịch vụ si cho bởi ri (si ) = pi si , ∀ i = 1..N . Còn chi phí được xác định thông qua hàm phi tuyến biểu diễn quan hệ giữa chi phí bồi thường bi và độ trễ chênh lệch giữa mức độ yêu cầu Di (si ) và khả năng đáp ứng trên mỗi dịch vụ di là ci (si ) = bi Di (si ) e βi (Di (si )−di ), ∀ i = 1..N . Sự ảnh hưởng của chi phí, băng thông và ngưỡng trễ đến hàm mục tiêu là một hàm phi tuyến được xác định dựa trên các đặc trưng của bài toán. Khi một dịch vụ bị trễ hàng đợi lớn hơn so với SLA cam kết thì hàm chi phí sẽ bị thay đổi rất lớn bởi phụ thuộc dưới dạng hàm mũ
8
S i=1 i=1
(Di (si ) > di ). Kallitsis đã chứng minh được bài toán trên có hàm mục tiêu là một hàm lồi [14]. Trong [30], Yeganeh cùng các cộng sự đã đề xuất thuật toán PSO để giải quyết bài toán trên. Tuy nhiên, phương án tối ưu gần đúng tìm được còn sai lệch khá nhiều so với phương án tối ưu thực sự.
2.2.2 Tối ưu định vị tài nguyên tập trung cho các lớp dịch vụ
2.2.2.1 Đề xuất thuật toán ACO-ĐVTN
Để biểu diễn N loại dịch vụ khác nhau, mỗi con kiến được mã hóa bằng vectơ k = {s1, s2, ..., sN }. Các cá thể kiến trong đàn được sinh ngẫu nhiên với si là tỷ lệ giữa các các dịch vụ được phân phối đều ngẫu nhiên trong đoạn [0, 1]. Ma trận mùi τn×n, τij thể hiện sự di chuyển của các con kiến là độ chênh lệch chi phí giữa 2 dịch vụ được cung cấp và được xác định bởi τij = [ri (si ) −ci (si )] − [rj (sj ) −cj (sj )]. Đường đi của mỗi con kiến thể hiện việc cập nhật vết mùi trên các cạnh. Mỗi cạnh của đồ thị mô tả mức độ mùi được lưu lại, tại mỗi nút con kiến k sẽ quyết định nút tiếp theo trong đường đi dựa vào vị trí hiện thời tại nút i và xác suất lựa chọn nút tiếp theo để di chuyển được xác định bởi (??). Trong đó, τij là vết mùi trên cạnh nối từ nút dịch vụ si đến dịch vụ sj , α là hệ số điều chỉnh ảnh hưởng của τij ; ηij là thông tin heuristic giúp đánh giá chính xác sự lựa chọn của con kiến khi di chuyển, β là hệ số điều chỉnh ảnh hưởng của ηij ; N k là các lân cận mà con kiến i k chưa thăm khi cấp phát tài nguyên cho dịch vụ si . Sau mỗi vòng lặp, vết mùi trên mỗi cạnh được cập nhật lại theo công thức (??) với ∆τ k
N (cid:80) i=1
là lượng mùi con kiến k để lại khi đi chuyển từ việc cấp phát tài nguyên cho dịch vụ si sang cấp phát tài nguyên cho dịch vụ sj . Khi đó, hàm đo độ thích nghi của con kiến k được tính theo (2.10).
2.2.2.2 Đề xuất thuật toán MMAS-ĐVTN
Thuật toán 2.1 MMAS-Định vị tài nguyên tập trung cho các lớp dịch vụ
Begin
Thiết lập tham số Khởi tạo:
Khởi tạo vết mùi τij = τmax , ∀ τij ; i = 1 ; Gbest ⇐ ∅ ; Repeat
Ibest ⇐ ∅ ; For each ant k = 1...K do Xây dựng phương án s k ; If (Ibest = ∅) then Ibest ⇐ s k ; If f (Ibest ) < f (s k ) then
;
Ibest ⇐ s k ; Cập nhật vết mùi theo Ibest : τij ← (1−ρ)τij +∆τ best
ij
end if
end for If (Gbest = ∅) then Gbest ⇐ Ibest ; If (f (Gbest ) < f (Ibest ) then
;
Gbest ⇐ Ibest ; Cập nhật vết mùi theo Gbest : τij ← (1−ρ)τij +∆τ best
ij
end if
Giới hạn vết mùi và cập nhật τmin và τmax ; Until (i > NMax ) or (Tìm thấy phương án tối ưu) ; s ∗ ⇐ Gbest ; Tính hàm mục tiêu f (s ∗) theo (2.10) ;
End
9
1 j = max (ri (si )−ci (si ))
2.2.3 Kết quả thực nghiệm và đánh giá
Quá trình thực nghiệm được tiến hành trên bộ dữ liệu lấy từ [14], các thuật toán được khai báo và cài đặt trên ngôn ngữ C với tham số là: K = 100,Nmax = 500, α = 1, β = 10, ρ = 0.5, τmin = 0.01, τmax = 0.5. Xét hệ thống đơn giản với 2 lớp dịch vụ (s1, s2) với giá trị tham số của các lớp dịch vụ thực nghiệm là:pi = 1, bi = 0.1, di = 0.01,QoS(= ε)=10−6, ¯αi = 0.2, σi = 0.01, βi = 10,Hi = 0.7 và C = 10Mbps [14]. Để chứng minh hiệu quả của các thuật toán đề xuất, các kết quả thực nghiệm chúng được đánh giá dựa trên phương án phân bố tài nguyên và hàm mục tiêu tối ưu nhất tìm được của các thuật toán PSO [30], ACO-ĐVTN và MMAS-ĐVTN so với phương án tối ưu thực sự trong [14].
1 , s ∗ 1 , s ∗ 2 ) và hàm mục tiêu f (s ∗
1 , s ∗
1 , s ∗
Thực nghiệm 1 đánh giá sự ảnh hưởng của tốc độ đến trung bình tới hàm mục tiêu. Bảng 2.4 so sánh kết quả thực nghiệm dựa trên phương án cấp phát tài nguyên tối ưu cho các lớp dịch vụ (s ∗ 2 ) tốt nhất của các thuật toán sau 50 lần thực hiện. Thực nghiệm 2 đánh giá sự ảnh hưởng của ngưỡng trễ tới hàm mục tiêu. Các phương án cấp phát tài nguyên tối ưu cho dịch vụ (s ∗ 2 ) được thể hiện trong Bảng 2.5. Sự nhạy cảm của hàm mục tiêu so với ngưỡng trễ di được xác định bởi ∂f = bi βi Di e βi (Di −di ) > 0. Thực nghiệm 3 ∂di đánh giá sự ảnh hưởng của chi phí tới hàm mục tiêu. Các phương án cấp phát tài nguyên tối ưu cho dịch vụ (s ∗ 2 ) được thể hiện trong Bảng 2.6 tuân theo qui luật phân bố tỷ lệ p1/p2. Thực nghiệm 4 đánh giá sự ảnh hưởng của tham số Hurst tới hàm mục tiêu, chúng ta cho thay đổi giá trị của tham số Hi trong khi các tham số khác được giữ cố định. Mức độ thay đổi các phương án cấp phát tài nguyên tối ưu cho dịch vụ (s ∗ 2 ) được thể hiện trong Bảng 2.7, hàm mục tiêu tỷ lệ nghịch với sự thay đổi của |∆Hi |. Để kiểm chứng về hiệu năng thực thi, luận án đã thống kê và so sánh thời gian thực hiện trung bình của các thuật toán trên 17 bộ test trong Hình 2.4.
Hình 2.4 – So sánh thời gian thực thi của PSO, ACO-ĐVTN và MMAS-ĐVTN
Thực nghiệm 5: Kết quả so sánh giá trị hàm mục tiêu và phân bố của thuật toán MMAS-ĐVTN so với phương án tối ưu thực sự khi thay đổi các tham số ¯αi , ∀ i = 1..6, pi , ∀ i = 1..6 [14] được cho trong Bảng 2.8và Bảng 2.9. Thực nghiệm 6 so sánh giá trị hàm mục tiêu trong 3 trường hợp tốt nhất, trung bình và tồi nhất giữa các thuật toán sau 50 lần thực hiện với số lớp dịch vụ tăng dần được cho trong Bảng 2.10. Hình 2.5 thể hiện so sánh thời gian thực thi trung bình giữa các thuật toán. Thực nghiệm cũng chỉ ra rằng, thuật toán MMAS-ĐVTN tốt hơn so với 2 thuật toán còn lại ở cả tính khám phá, độ ổn định và thời gian thực thi khi áp dụng trên nhiều lớn dịch vụ.
10
1 , s ∗
Bảng 2.4 – So sánh kết quả phân bố tài nguyên khi thay đổi tốc độ đến trung bình (¯α1, ¯α2) giữa PSO, ACO-ĐVTN và MMAS-ĐVTN
PSO [30] Phương án tối ưu* [14] (s ∗ MMAS-ĐVTN (s ∗ Sai số 1 , s ∗ 2 )
1 , s ∗ 2 ) (0.5, 0.5) (0.5462, 0.4538) (0.5911, 0.4089) (0.5215, 0.4785) (0.4532, 0.5467)
1 , s ∗ 2 ) (0.5, 0.5) (0.5446, 0.4554) (0.5718, 0.4282) (0.5213, 0.4787) (0.4532, 0.5467)
Bảng 2.5 – So sánh kết quả phân bố tài nguyên khi thay đổi ngưỡng trễ (d1, d2) giữa PSO, ACO-ĐVTN và MMAS-ĐVTN
Test #1 #2 #3 #4 #5 Tham số ¯α2 ¯α1 0.2 0.2 0.2 0.3 0.2 0.4 0.3 0.4 0.5 0.4 f (s ∗) 9.957 9.931 9.869 7.872 6.782 ACO-ĐVTN 1 , s ∗ (s ∗ 2 ) (0.5, 0.5) (0.5446, 0.4554) (0.5893, 0.4107) (0.5198, 0.4802) (0.4803, 0.5197) f (s ∗) 9.957 9.936 9.815 7.822 6.725 f (s ∗) 9.957 9.936 9.885 8.214 6.782 (s ∗ 1 , s ∗ 2 ) (0.5, 0.5) (0.5446, 0.4554) (0.5873, 0.4127) (0.5275, 0.4725) (0.4516, 0.5484) f (s ∗) ∆f (s ∗ 9.957 9.936 9.897 8.238 6.796 0.000 0.000 0.012 0.024 0.014 (%) 0.00% 0.00% 0.12% 0.29% 0.21%
PSO [30] Phương án tối ưu* [14] (s ∗ MMAS-ĐVTN (s ∗ (s ∗ Sai số 1 , s ∗ 2 )
1 , s ∗ 2 ) (0.5158, 0.4842) (0.5195, 0.4805) (0.5076, 0.4924) (0.5293, 0.4707)
1 , s ∗ 2 ) (0.5327, 0.4673) (0.5195, 0.4805) (0.5231, 0.4769) (0.5375, 0.4625)
1 , s ∗ 2 ) (0.5327, 0.4673) (0.5195, 0.4805) (0.5265, 0.4735) (0.5488, 0.4512)
Bảng 2.6 – So sánh kết quả phân bố tài nguyên khi thay đổi thừa số giá (p1, p2) giữa giữa PSO, ACO-ĐVTN và MMAS-ĐVTN
1 1
Test #6 #7 #8 #9 Tham số d2 d1 0.03 0.01 0.06 0.01 0.09 0.01 0.12 0.01 f (s ∗) 9.956 9.968 9.858 9.982 ACO-ĐVTN 1 , s ∗ (s ∗ 2 ) (0.5217, 0.4673) (0.5187, 0.4813) (0.5102, 0.4898) (0.5375, 0.4625) f (s ∗) 9.961 9.965 9.881 9.975 f (s ∗) 9.965 9.968 9.971 9.975 f (s ∗) ∆f (s ∗ 9.969 9.968 9.978 9.982 0.004 0.000 0.008 0.007 (%) 0.04% 0.00% 0.17% 0.07%
PSO [30] Phương án tối ưu* [14] (s ∗ MMAS-ĐVTN (s ∗ (s ∗ Sai số 1 , s ∗ 2 )
1 , s ∗ 2 ) (0.3049, 0.6951) (0.6951, 0.3049) (0.6527, 0.3473) (0.7298, 0.2702) (0.5723, 0.4277) (0.5, 0.5) (0.245, 0.755)
1 , s ∗ 2 ) (0.3108, 0.6892) (0.6892, 0.3108) (0.6534, 0.3466) (0.7183, 0.2817) (0.5748, 0.4252) (0.5, 0.5) (0.257, 0.743)
1 , s ∗ 2 ) (0.3083, 0.6917) (0.6917, 0.3083) (0.6534, 0.3466) (0.7183, 0.2817) (0.5748, 0.4252) (0.5, 0.5) (0.276, 0.724)
Bảng 2.7 – Ảnh hưởng của tham số Hurst Hi (i = 1, 2) đến hàm mục tiêu
Test #10 #12 #13 #14 #15 #16 #17 Tham số p1 1 2 3 4 4 4 4 p2 2 1 2 1 3 4 8 f (s ∗) 16.27 16.27 39.05 30.15 45.63 39.96 64.81 ACO-ĐVTN (s ∗ 1 , s ∗ 2 ) (0.3108, 0.6892) (0.6892, 0.3108) (0.6534, 0.3466) (0.7231, 0.2769) (0.5748, 0.4252) (0.5, 0.5) (0.257, 0.743) f (s ∗) 16.34 16.34 39.17 30.66 45.75 39.96 65.72 f (s ∗) 16.34 16.34 39.17 30.69 45.75 39.96 65.72 f (s ∗) ∆f (s ∗ 0.18 16.52 0.18 16.52 0.00 39.17 0.00 30.69 0.00 45.75 0.00 39.96 2.18 67.90 (%) 1.08% 1.08% 0.00% 0.00% 0.00% 0.00% 3.21%
1 , s ∗ 2 )
Độ lệch (cid:12) Test (s ∗ Sai số (%) Hi fMMAS(s ∗ (cid:12) (cid:12) Độ lệch |∆si | (cid:12)∆Hi
1 , s ∗ 2 ) (0.5000, 0.5000) (0.4947, 0.5053) (0.488, 0.512) (0.4796, 0.5204) (0.4737, 0.5263) (0.5062, 0.4939)
#18 #19 #20 #21 #22 #23 0.80 0.78 0.75 0.70 0.65 0.82 0.00 0.02 0.05 0.10 0.15 0.02 0.0000 0.0053 0.0120 0.0204 0.0263 0.0062 8.79576 8.96289 9.13588 9.31354 9.42257 8.55904 ftối ưu* [14] 8.79576 8.96289 9.13588 9.31354 9.42257 8.55904 0.00 (0%) 0.00 (0%) 0.00 (0%) 0.00 (0%) 0.00 (0%) 0.00 (0%)
Bảng 2.8 – So sánh kết quả phân bố tài nguyên của thuật toán MMAS-ĐVTN so với phương án tối ưu thực sự khi thay đổi tốc độ đến trung bình ¯α = (¯α1, ¯α2, ¯α3, ¯α4, ¯α5, ¯α6) của các dịch vụ
Tham số MMAS-ĐVTB Phương án tối ưu [14] Sai số Test f (s ∗) f (s ∗) ∆f (s ∗) (%) ¯α = ( ¯α1, ¯α2, ¯α3, ¯α4, ¯α5, ¯α6)
Bảng 2.9 – So sánh kết quả phân bố tài nguyên của thuật toán MMAS-ĐVTN so với phương án tối ưu thực sự khi thay đổi tham số giá p = (p1, p2, p3, p4, p5, p6) của các dịch vụ
#24 #25 #26 #27 #28 #29 #30 #31 #32 0.10, 0.10, 0.10,0.10, 0.10, 0.10 0.11, 0.10, 0.10, 0.10, 0.10, 0.10 0.12, 0.11, 0.10, 0.10, 0.10,0.10 0.13, 0.12, 0.11, 0.10, 0.10 ,0.10 0.13, 0.12, 0.11, 0.11, 0.10, 0.10 0.13, 0.12, 0.11, 0.11, 0.12, 0.13 0.13, 0.12, 0.11, 0.12, 0.13, 0.14 0.10, 0.11, 0.12, 0.13, 0.14, 0.15 0.10, 0.11, 0.12, 0.13, 0.14, 0.20 s ∗ = (s1, s2, s3, s4, s5, s6) 0.167, 0.167, 0.167, 0.167, 0.167, 0.167 0.172, 0.166, 0.166, 0.165, 0.165, 0.165 0.177, 0.174, 0.163, 0.162, 0.162, 0.162 0.180, 0.178, 0.168, 0.159, 0.158, 0.158 0.178, 0.171, 0.167, 0.167, 0.157, 0.156 0.175, 0.167, 0.159, 0.158, 0.168, 0.176 0.169, 0.160, 0.155, 0.162, 0.171, 0.180 0.145, 0.156, 0.163, 0.171, 0.179, 0.188 0.140, 0.149, 0.157, 0.162, 0.170 , 0.221 83.74 81.66 78.38 72.75 69.23 47.84 21.19 20.78 -125.12 s ∗ = (s1, s2, s3, s4, s5, s6) 0.167, 0.167, 0.167, 0.167, 0.167, 0.167 0.174, 0.165, 0.165, 0.165, 0.165, 0.165 0.180, 0.171, 0.162, 0.162, 0.162, 0.162 0.185, 0.176, 0.167, 0.158, 0.158, 0.158 0.183, 0.174, 0.165, 0.165, 0.156, 0.156 0.176, 0.167, 0.158, 0.158, 0.167, 0.176 0.171, 0.162, 0.153, 0.162, 0.171, 0.180 0.144, 0.153, 0.162, 0.171, 0.180, 0.190 0.136, 0.145, 0.154, 0.163, 0.173 , 0.229 83.74 82.50 79.52 73.42 70.79 49.09 21.73 21.18 -122.60 0.00 0.84 1.14 0.67 1.59 1.25 0.54 0.40 2.52 0.00 1.02 1.43 0.91 2.20 2.55 2.49 1.89 2.06
1 2
Tham số Phương án tối ưu [14] Sai số Test f (s ∗) f (s ∗) ∆f (s ∗) (%) p = (p1, p2, p3, p4, p5, p6)
Bảng 2.10 – Kết quả thực nghiệm so sánh 3 thuật toán PSO, ACO-ĐVTN và MMAS-ĐVTN trên nhiều lớp dịch vụ
#33 #34 #35 #36 #37 #38 #39 #40 2.00, 1.00, 1.00, 1.00, 1.00, 1.00 3.00, 2.00, 1.00, 1.00, 1.00, 1.00 4.00, 3.00, 2.00, 1.00, 1.00, 1.00 5.00, 4.00, 3.00, 2.00, 1.00, 1.00 6.00, 5.00, 4.00, 3.00, 2.00, 1.00 6.00, 5.00, 4.00, 3.00, 2.00, 6.00 6.00, 5.00, 4.00, 3.00, 2.00, 7.00 6.00, 5.00, 4.00, 3.00, 8.00, 7.00 MMAS-ĐVTB s ∗ = (s1, s2, s3, s4, s5, s6) 0.178, 0.165, 0.164, 0.164, 0.164, 0.164 0.190, 0.169, 0.161, 0.160, 0.160, 0.160 0.198, 0.167, 0.164, 0.157, 0.157, 0.156 0.201, 0.167, 0.160, 0.158, 0.156, 0.156 0.203, 0.170, 0.160, 0.159, 0.155, 0.154 0.181, 0.166, 0.159, 0.155, 0.155, 0.182 0.167, 0.163, 0.158, 0.155, 0.154, 0.202 0.160, 0.159, 0.157, 0.156, 0.203, 0.167 100.67 134.88 186.25 253.14 339.36 418.73 434.55 529.81 s ∗ = (s1, s2, s3, s4, s5, s6) 0.179, 0.164, 0.164, 0.164, 0.164, 0.164 0.193, 0.167, 0.160, 0.160, 0.160, 0.160 0.202, 0.168, 0.161, 0.156, 0.156, 0.156 0.206, 0.169, 0.161, 0.156, 0.154, 0.154 0.208, 0.169, 0.161, 0.157, 0.154, 0.152 0.183, 0.166, 0.159, 0.155, 0.153, 0.183 0.169, 0.161, 0.157, 0.154, 0.152, 0.208 0.161, 0.157, 0.154, 0.152, 0.208, 0.169 100.94 136.09 188.66 257.66 342.40 422.80 442.40 542.40 0.27 1.21 2.40 4.52 3.04 4.07 7.85 12.6 0.27 0.89 1.27 1.75 0.89 0.96 1.86 2.32
Số lớp
Tốt nhất
Trung bình
Xấu nhất
Tốt nhất
Trung bình
Xấu nhất
Tốt nhất
Trung bình
Xấu nhất
PSO ACO-ĐVTN MMAS-ĐVTN
8 10 12 16 20 24 28 32 36 40 100.53 125.21 153.63 210.68 256.11 315.37 417.58 512.68 652.95 751.53 99.17 122.24 151.21 207.97 252.00 311.90 415.10 510.36 649.31 748.03 97.39 120.16 150.27 204.20 249.55 309.16 411.33 508.51 648.29 747.22 100.53 125.21 156.26 216.26 256.63 319.89 419.32 513.47 653.21 760.16 99.79 123.97 154.07 214.62 253.28 316.72 417.79 511.28 651.07 757.38 98.28 121.08 151.06 212.98 251.67 313.86 414.45 509.41 650.84 755.35 100.53 125.21 156.26 221.74 255.68 327.37 420.32 513.47 654.32 757.63 100.29 124.24 154.79 219.69 253.55 324.03 418.83 511.72 652.28 755.24 99.78 121.26 153.10 218.88 252.16 317.16 417.24 510.76 649.57 752.20
Hình 2.5 – So sánh thời gian thực thi của PSO, ACO-ĐVTN và MMAS-ĐVTN
Như vậy, bài toán tối ưu cấp phát tài nguyên tập trung cho các lớp dịch vụ rất phức tạp với sự ảnh hưởng và tác động lẫn nhau của rất nhiều tham số tác động đến hàm mục tiêu của bài toán. Trong mục này, luận án đã đề xuất được thuật toán ACO-ĐVTN và MMAS-ĐVTN cho phép tìm nghiệm gần tối ưu với sai số rất nhỏ so với nghiệm tối ưu thực trong thời gian tuyến tính có khả năng áp dụng đối với mô hình có số lớp dịch vụ lớn.
2.3 Đáp ứng tài nguyên cho các luồng đa phương tiện
2.3.1 Mô hình bài toán
Mô hình bài toán tối ưu QoS cho các luồng đa phương tiện theo mô hình
Q-MOF [15] được định nghĩa như sau:
Định nghĩa 2.3 (Tối ưu QoS cho các luồng đa phương tiện [15]).
(2.12)
max
wi xij ui (rij )
n (cid:88) pi(cid:88)
thỏa mãn các ràng buộc:
i=1 j =1
(2.13)
xij rijk (cid:54) Bdownlink
h (cid:88) pi(cid:88) q (cid:88)
j =1
(2.14)
xij rijk (cid:54) Buplink
i=1 n (cid:88) k =1 q (cid:88) pi(cid:88)
j =1 i=h+1 k =1
(2.15)
xij rijk (cid:54) Rk , ∀ k = q+1, .., m
n (cid:88) pi(cid:88)
i=1 j =1
(2.16)
xij rijk (cid:54) Rik , ∀ k = 1..m, ∀ i = 1..n
pi(cid:88)
j =1
(2.17)
xij = 1
n (cid:88) pi(cid:88)
(2.18)
xij ∈ {0, 1} , ∀ i = 1..n, ∀ j = 1..pi
13
i=1 j =1
2.3.2 Đề xuất thuật toán MMAS tối ưu QoS luồng đa phương tiện
Đồ thị cấu trúc có dạng hình cây phụ thuộc vào số lượng luồng n và số lượng tham số chất lượng dịch vụ pi được yêu cầu trên mỗi luồng fi . Khi bắt đầu quá trình tìm kiếm, kiến có thể tìm trong các nhóm có phạm vi nhỏ nên số khả năng lựa chọn là không nhiều. Sau đó các con kiến sẽ liên kết lại với nhau để sinh ra các lựa chọn mới. Khi đó, phương án của bài toán sẽ là một tập các đối tượng S = (cid:8)oij | xoij = 1(cid:9) sao cho xoij = 1 có nghĩa là đối tượng oij được lựa chọn và tương ứng với việc biến quyết định xij = 1. Ta xây dựng phương án S = {oi1j1, ..., oin jn } với các vết mùi được lưu trên từng đối tượng. Vết mùi τij sẽ đặc trưng cho mối quan hệ với đối tượng oij . Điểm quan trọng nhất để xây dựng lời giải và việc kết hợp và khám phá tri thức dựa trên thông tin heuristic để bổ sung các thành phần mới vào cấu trúc lời giải. Gọi Sk là tập các đối tượng được chọn tại vòng lặp thứ k , C (Candidates) là tập tất cả các luồng trong nhóm đang chọn không vi phạm các ràng buộc về tài nguyên, τSk là thông số heuristic động của vết mùi của các đối tượng trong Sk , ηSk là thông tin heuristic giúp đánh giá việc lựa chọn Sk , α và β là các hệ số điều chỉnh ảnh hưởng. Hàm mục tiêu đánh giá mỗi phương án được tính bởi (2.12). Thuật toán MMAS tối ưu giám sát QoS cho các luồng đa phương tiện (MMAS-Q.MOF) được mô tả như sau:
Thuật toán 2.2 MMAS-Q.MOF
Các tham số: α, β, ρ, k . Số lượng kiến: K . Số vòng lặp tối đa NMax . Giới hạn vết mùi: τmin , τmax . Khởi tạo vết mùi cho tất cả các đối tượng và nhóm là τmax ; Topksolution ⇐ {Lưu lại k phương án tốt nhất} ; i = 1 ; Repeat
SGbest ⇐ ∅ ; For kiến k = 1...K do
SIbest ⇐ ∅ ; C ⇐ Tất cả các nhóm luồng dịch vụ ; While C (cid:54)= ∅ do
;
Cg ⇐ Chọn nhóm có vết mùi cao nhất trong tập C ; Candidates ⇐ {oij ∈ Cg thỏa mãn các ràng buộc (2.13-2.16)} Cập nhật giá trị heuristic cục bộ: sk (Oij ) = wi ui (rij )
(l)
rijl dSk
m (cid:80) i=1
Chọn đối tượng oij ∈ C với xác suất PSk (Oij ) =
[τSk (Oij )]α[ηSk (Oij )]β ;
[τSk (Oij )]α[ηSk (Oij )]β (cid:80) Oij ∈C
Sk ⇐ Sk ∪oij ; Loại bỏ Cg khỏi tập C ;
Endwhile If f (Sk ) > f (SIbest ) then SIbest ⇐ Sk ;
Endfor If f (SGbest ) < f (SIbest ) then SGbest ⇐ SIbest ; Cập nhật cơ sở dữ liệu vết mùi và giá trị cận biên τmin và τmax ; i = i +1 ;
Until (i > NMax ) or (giải pháp tối ưu được tìm thấy) ;
Để nâng cao hiệu quả của thuật toán MMAS ở trên, luận án đã thử nghiệm cách tiếp cận tương tự nhưng sử dụng các phương pháp cập nhật vết mùi mới là MLAS, SMMAS và 3LAS được đề xuất trong [23].
2.3.3 Kết quả thực nghiệm và đánh giá
Mô hình thực nghiệm tối ưu QoS các luồng dịch vụ đa phương tiện giữa hai nút mạng ứng của 2 người dùng đầu cuối với n luồng đa phương tiện với các chỉ tiêu chất lượng khác nhau. Các thuật toán được khai báo và cài đặt trên ngôn
14
.
ngữ C với tham số thực nghiệm là: K = 100,Nmax = 500, α = 1, β = 5, ρ = 0.5, k = 10, τmin = 0.01, τmax = 8, τmid = τmax −τmin
Thực nghiệm 1 trên bộ dữ liệu IMS Testbed lấy từ [15–17] với các tham số cần đáp ứng trên các dịch vụ AVC được yêu cầu được mô tả trong Bảng 2.11 và Bảng 2.13 [17]. Kết quả so sánh hàm mục tiêu và thời gian thực thi trung bình của thuật toán MMAS trong 50 lần thực hiện với phương án tối ưu được giải trên công cụ GLPK [10] được cho trong Bảng 2.14. Thực nghiệm 2trên bộ dữ liệu thực nghiệm gồm 10 bài toán được sinh ngẫu nhiên với các tham số chi tiết về số lượng luồng theo hướng downlink và uplink được cho trong Bảng 2.15. Các giá trị tiện tích của mỗi luồng phân bố theo tài nguyên yêu cầu ui (rij ) ∈ [0, 1], Bdownlink = 1200 kbps, Buplink = 800 kbps. Kết quả thực nghiệm được so sánh chi tiết được cho trong Bảng 2.16. Thực nghiệm 3 cài đặt cải tiến thuật toán MMAS kết hợp với 3 qui tắc cập nhật vết mùi mới là MLAS, SMMAS và 3LAS [23]. Bằng thực nghiệm chúng ta có thể thấy được ưu điểm khi sử dụng SMMAS và 3-LAS so với MMAS trong Bảng 2.16. Kết quả so sánh về thời gian thực thi giữa các thuật toán được cho trong Hình 2.7.
Hình 2.6 – So sánh thời gian thực thi giữa các thuật toán trên các luồng
2.4 Kết chương
Trong Mục 2.2, luận án tập trung nghiên cứu bài toán tối ưu cấp phát tài nguyên cho các lớp dịch vụ có xét đến yêu cầu về QoS. Thuật toán MMAS đề xuất đã khắc phục được hạn chế của các phương pháp tất định sử dụng tính chất giải tích của hàm mục tiêu và ràng buộc không hiệu quả khi số lượng lớp dịch vụ tăng và đánh giá được sự ảnh hưởng của các tham số trong lớp dịch vụ đến hàm mục tiêu. Bài toán toán tối ưu tài nguyên cho các luồng đa phương tiện đảm bảo yêu cầu về QoS được đề cập đến trong Mục 2.3. Mục tiêu hướng đến là xây dựng cấu hình cấp phát tài nguyên mạng cho người dùng thỏa mãn các ràng buộc đã cam kết theo trọng số có thể dùng để biểu diễn tương đối mức độ đáp ứng dịch vụ cho một luồng dữ liệu với mục tiêu cực đại hàm chi phí thu được. Thuật toán MMAS đề xuất cho phép tối ưu tài nguyên cho các luồng đa phương tiện đảm bảo yêu cầu về QoS của các ứng dụng đa phương tiện có thể áp dụng trên nhiều luồng dịch vụ đa phương tiện với số lượng ràng buộc lớn.
15
2
Bảng 2.11 – Tập tham số yêu cầu và ràng buộc của các luồng dịch vụ AVC
Tập tham số đáp ứng Dịch vụ yêu cầu Người dùng A Người dùng B Ràng buộc audio, video, image, model Ngdùng A, B: audio, video, data, image, text audio, video, data, image, model audio: peg, pcm, gsm Not Allowed (N/A):audio, G729, G723 Thành phần đa phương tiện Codecs p1 p2
Băng thông Downlink tối thiểu Trễ Downlink, Uplink tối đa Biến thiên trễ Downlink, Uplink tối đa
Bảng 2.12 – Tập tham số các luồng đa phương tiện thực nghiệm
Băng thông Uplink tối thiểu Độ phân giải cục bộ Độ phân giải từ xa audio, video, data audio: mpeg, gsm ; video: mpeg, h26 46 150 10 1 46 176x144 176x144 1200 150 N/A N/A 800 1204x768 N/A audio: peg, video: mpeg, mjpeg, h263 1300 150 N/A N/A 1000 N/A 1204x768 1400 N/A N/A N/A 1400 N/A N/A p3 p4,p8 p5,p9 p6, p10 Mất gói Downlink, Uplink tối đa p7 p11 p12
1 6
Tập tham số dịch vụ Giá trị
Bảng 2.13 – Tài nguyên yêu cầu và chi phí đáp ứng các luồng đa phương tiện
Tập các luồng đa phương tiện Luồng dữ liệu thoại (audio) và dữ liệu hình (video) theo hướng downlink và uplink Các điểm hoạt động của các luồng Giá trị tiện tích của mỗi luồng phân bố theo tài nguyên yêu cầu Băng thông downlink giới hạn Đơn vị tính giá thành trên mỗi bit dữ liệu Chi phí tối đa truyền dữ liệu Chi phí băng thông của lớp q F = (f1, f2, f3, f4) ({f1}, {f2}) và ({f3}, {f4}) P = (p1, p2, p3, p4) = (3, 8, 3, 8) ui (rij ) ∈ [0, 1] Bdownlink = 1200 kbps, Buplink = 800 kbps 10 [unit/bit] 20000 [unit/s] [bit/s] x chi phí lớp q [unit/b]
Tham số hoạt động Luồng Tài nguyên Băng thông (kbps) rij 1 Chi phí rij 2 Lợi nhuận ui (rij )
f1, f3
f2, f4
codec: GSM, tốc độ lấy mẫu: 8000, tốc độ bits trên 1 mẫu: 8 codec: MPEG, tốc độ lấy mẫu: 22050, tốc độ bits trên 1 mẫu: 16 codec: MPEG, tốc độ lấy mẫu: 44100, tốc độ bits trên 1 mẫu: 16 codec: MPEG, sample rate: 44100, tốc độ bits trên 1 mẫu: 16 codec: H263, độ phân giải: 176x144, tốc độ truyền khung hình: 15 codec: MJPEG, độ phân giải: 176x144, tốc độ truyền khung hình: 5 codec: MJPEG, độ phân giải: 176x144, tốc độ truyền khung hình: 10 codec: MJPEG, độ phân giải: 176x144, tốc độ truyền khung hình: 15 codec: MJPEG, độ phân giải: 352x288, tốc độ truyền khung hình: 5 codec: MJPEG, độ phân giải: 352x288, tốc độ truyền khung hình: 15 codec: MJPEG, độ phân giải: 352x288, tốc độ truyền khung hình: 30 21 34 64 25 90 370 400 781 1015 1400 2000 210 340 640 900 900 3700 4000 7810 10150 14000 20000 0.5 0.8 1.0 0.2 0.4 0.5 0.6 0.7 0.8 0.9 1.0 r11 r12 r13 r21 r22 r23 r24 r25 r26 r27 r28
Bảng 2.14 – So sánh hàm mục tiêu và thời gian thực thi của thuật toán MMAS-QMOF với công cụ GLPK trên bộ dữ liệu chuẩn
Thuật toán MMAS-QMOF Công cụ GNU Linear Programming Kit Sai số (%) Hiệu quả (%)
Vòng lặp Phân bố tài nguyên Hàm mục tiêu Thời gian (giây) Phân bố tài nguyên Hàm mục tiêu Thời gian (giây) Hàm mục tiêu Thời gian
Bảng 2.15 – Tham số về số lượng luồng theo hướng downlink và uplink thực nghiệm
93 128 187 264 331 375 417 2.770 2.839 2.840 2.840 2.909 2.909 2.980 0.583 0.597 0.615 0.628 0.639 0.646 0.652 2.770 2.839 2.840 2.840 2.909 2.909 2.980 0.625 0.633 0.641 0.659 0.670 0.677 0.683 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 6.72% 5.69% 4.06% 4.70% 4.63% 4.58% 4.54% (r13, r23, r33, r44) (r13, r25, r33, r43) (r13, r26, r33, r42) (r13, r24, r33, r44) (r13, r25, r33, r44) (r13, r26, r33, r43) (r13, r26, r33, r44) (r13, r23, r33, r44) (r13, r25, r33, r43) (r13, r26, r33, r42) (r13, r24, r33, r44) (r13, r25, r33, r44) (r13, r26, r33, r43) (r13, r26, r33, r44)
1 7
Số luồng Tham số thực thi Test Downlink (f1, ..., fh ) Uplink (fh+1, ..., fn ) Downlink (p1, ..., ph ) Uplink (ph+1, ..., pn )
Bảng 2.16 – So sánh kết quả thực thi giữa thuật toán MMAS-QMOF, SMMAS-QMOF, MLAS-QMOF và 3-LAS-QMOF
#1 #2 #3 #4 #5 #6 #7 #8 #9 #10 (2) (3) (4) (3, 8) (3, 7, 4) (6, 8, 9) (10, 15) (10, 15, 20, 25) (15, 20, 30) (20, 25, 30, 35, 45) (2) (4) (2, 5, 7) (3, 8) (9) (8, 5, 4) (8, 10, 12, 13) (10, 15, 20, 25) (20, 10, 30, 25, 15) (40, 35, 50) {f1} {f1} {f1} {f1, f2} {f1, f2, f3} {f1, f2, f3} {f1, f2} {f1, f2, f3, f4} {f1, f2, f3} {f1, f2, f3, f4, f5} {f2} {f2} {f2, f3, f4} {f3, f4} {f4} {f4, f5, f6} {f3, f4, f5, f6} {f5, f6, f7, f8} {f4, f5, f6, f7, f8} {f6, f7, f8}
MMAS-QMOF SMMAS-QMOF MLAS-QMOF 3-LAS-QMOF GLPK Test Tốt nhất Trung bình Tồi nhất Tốt nhất Trung bình Tồi nhất Tốt nhất Trung bình Tồi nhất Tốt nhất Trung bình Tồi nhất Tối ưu
#1 #2 #3 #4 #5 #6 #7 #8 #9 #10 1.752 1.965 2.786 2.980 2.863 4.792 4.937 10.573 11.218 10.983 1.866 2.515 3.386 3.235 3.263 5.342 5.537 11.123 11.268 11.183 1.982 3.065 3.836 3.905 3.188 5.492 6.137 11.498 11.343 11.418 1.752 1.965 2.786 2.980 2.863 4.792 4.937 10.573 11.218 10.983 1.797 2.325 2.826 3.427 2.943 4.912 5.438 11.093 11.738 11.263 1.891 2.458 3.337 3.976 3.423 5.179 6.048 11.337 12.205 11.596 1.752 1.965 2.786 2.980 2.863 4.792 4.937 10.573 11.218 10.983 1.781 2.398 3.219 3.281 3.230 5.092 5.104 11.006 11.351 11.183 1.884 2.578 3.339 3.560 3.630 5.112 5.144 11.466 11.671 11.503 1.752 1.965 2.786 2.980 2.863 4.792 4.937 10.573 11.218 10.983 1.792 2.015 3.136 3.305 3.013 5.042 5.062 10.623 11.393 11.191 1.863 2.393 3.203 3.861 3.080 5.198 5.573 10.645 11.704 11.552 1.752 1.965 2.786 2.980 2.863 4.792 4.937 10.573 11.218 10.983
Chương 3
An ninh dịch vụ trong mạng NGN
Bảo mật là một tham số mới nhưng rất quan trọng (trong một số trường hợp mức độ bảo mật có thể được xét ngay sau băng thông) bên cạnh tập các tham số để cung cấp QoS dịch vụ theo các mức ưu tiên khác nhau tới người dùng trước những hành động xâm nhập và tấn công mạng.
3.1 Kiến trúc đảm bảo ninh trong mạng NGN
Khuyến nghị X.805 [31] được ITU-T đưa ra nhằm cung cấp giải pháp an ninh đầu cuối áp dụng cho từng thiết bị với 3 lớp an ninh được định nghĩa đó lớp an ninh cơ sở hạ tầng, lớp an ninh các dịch vụ và lớp an ninh các ứng dụng. Tất cả những lớp an ninh này được xây dựng dựa vào nhau để tạo nên giải pháp an ninh tổng thể cho mạng. Cách thức xử lý theo mô hình phân lớp sẽ thực hiện như sau: các lỗ hổng an ninh được xử lý tại lớp an ninh cơ sở hạ tầng, sau đó xử lý tại lớp dịch vụ, cuối cùng các lỗ hổng an ninh được xử lý tại mức ứng dụng. Kiến trúc bảo mật nhằm khắc phục các lỗ hổng an ninh và giảm thiểu nguy cơ tấn công trong mạng NGN theo X.805 với 3 lớp an ninh và 8 biện pháp phòng chống.
3.2 Tấn công từ chối dịch vụ
Tấn công từ chối dịch vụ (Denial of Servcice-DoS) [9] được hiểu là một nỗ lực ngăn những người sử dụng dịch vụ hợp pháp hay cố gắng gây từ chối sự sẵn sàng của dịch vụ đến người dùng hợp pháp. Một cuộc tấn công DoS vào một ứng dụng dịch vụ Internet có thể thực hiện được bằng cách chiếm những tài nguyên quan trọng (băng thông mạng, bộ nhớ máy chủ, không gian lưu trữ, thời gian xử lý của CPU) phục vụ ứng dụng hoặc phục vụ truy cập đến ứng dụng đó để chặn ứng dụng hoạt động hoặc ngắt kết nối ứng dụng với Internet, làm cho ứng dụng không sẵn sàng với người dùng. Có hai mô hình chính là Agent-Handler và IRC-Based. Hiện nay các loại hình tấn công DDoS rất đa dạng với nhiều công cụ được sử dụng. Các hình thức tấn công được phân loại dựa vào các tiêu chí cụ thể có thêm xem trong [9]. Các cơ chế phòng thủ hiện tại đang cố gắng chặn tấn công DDoS bằng cách lọc lưu lượng tấn công (đưa lọc bổ sung trong bộ định tuyến ; kiểm tra tất cả các gói dữ liệu đến trên cơ sở đặc tính hóa lưu lượng, loại bỏ những gói tin bị nghi ngờ) tại mức định tuyến [6, 18].
3.3 Đề xuất giải pháp phòng chống dựa trên chính sách
Giải pháp phòng chống tấn công DDoS hiện nay có thể chia thành 3 kiểu: Dựa trên mã (Signature-based ), phòng thủ ngưỡng (Threshold defense) và kiểu kết hợp. Các dạng tấn công DDoS thực hiện tìm kiếm các lỗ hổng bảo mật trên các
18
máy tính kết nối tới Internet và khai thác các lỗ hổng bảo mật để xây dựng mạng Botnet gồm nhiều máy tính kết nối tới Internet. Do đó, tấn công rất khó để ngăn chặn hoàn toàn. Ngay cả khi tất cả các biện pháp phòng chống này được sử dụng, chúng vẫn tồn tại các vấn đề sau:
- Các gói tin tấn công đến Firewall có thể chặn lại, nhưng hầu hết chúng đều đến từ những địa chỉ IP chưa có trong tập luật của Firewall nên chúng được coi là những gói tin hợp lệ.
- Khi địa chỉ nguồn của gói tin bị giả mạo và không nhận được sự phản hồi từ những địa chỉ nguồn thật thì biện pháp ngăn chặn thông thường lá cấm giao tiếp với địa chỉ nguồn đó. Tuy nhiên mạng Botnet bao gồm từ hàng nghìn tới vài trăm nghìn địa chỉ IP trên Internet và điều đó là vô cùng khó khăn để ngăn chặn tấn công.
- Các cuộc tấn công làm cạn kiệt băng thông mạng được thực hiện trên các server trong mạng LAN. Khi máy chủ Web có hàng trăm Mbps kết nối Internet thì các biện pháp kiểm soát mức tiêu thụ băng thông mạng không còn hiệu quả trước các kiểu tấn công tràn UDP, ICMP vì lúc này lưu lượng được đẩy lên hàng Gbps. Biện pháp phòng chống tại mạng LAN không đủ để ngăn chặn các máy chủ đang ở tình trạng quá tải và tạo nên hiện tượng nghẽn mạng.
- Kiểu tấn công làm cạn kiệt tài nguyên và các biện pháp đối phó trên cũng có vấn đề khi các gói tin của người sử dụng thường xuyên trộn lẫn với các gói tin tấn công cũng có thể bị loại bỏ.
Giả thiết kiến trúc mạng NGN được xây dựng từ các ISP cho phép cung cấp các dịch vụ cá nhân mở rộng, các nút Router trong mạng có thể điều khiển được và ISP có thể phát hiện được các địa chỉ IP bất thường. Như đã phân tích ở trên, mục tiêu của các biện pháp phòng chống tấn công DDoS hướng đến là giảm thiểu thiệt hại tài nguyên của máy chủ. Nhưng tấn công DoS sử dụng UDP lại làm tăng băng thông các gói tin trên mạng được gửi đến máy chủ từ mạng LAN nên rất khó để chống lại. Các biện pháp phòng chống DoS sử dụng UDP hiệu nay vẫn chưa thực sự hiệu quả. Vì vậy mục tiêu phương pháp được đề xuất trong bài báo này hướng đến kiểm soát và ngăn chặn tấn công DoS dùng UDP. Đa số giao thức truyền thông trên mạng là TCP được sử dụng trong Web Servers và Mail Servers. Còn giao thức UDP được sử dụng bởi DNS và NTP truyền thông với lượng băng thông nhỏ. Giao thức báo hiệu điều khiển lớp ứng dụng SIP sử dụng băng thông rộng để thiết lập, duy trì, kết thúc các phiên truyền thông đa phương tiện sử dụng UDP và RTP. Tuy nhiên, đối với các dịch vụ UDP chúng ta rất khó đánh giá sự bình thường băng thông của mạng từ phía ISP.
Hướng tiếp cận của luận án là dùng chính sách an ninh riêng để phát hiện tấn công DoS bằng cách kiểm soát số lượng gói tin UDP phát sinh trong mạng NGN có vượt quá một giới hạn nhất định trong một đơn vị thời gian với băng thông sẵn có hay không ? Giới hạn này được xác định dựa trên chính sách an ninh riêng trên mạng LAN và được thiết lập trước khi tấn công DoS xảy ra.
1) Thiết lập chính sách an ninh riêng: Băng thông của Server dành cho các gói tin UDP trong một đơn vị thời gian được thiết lập thành tham số để điều
19
khiển tấn công DoS. Giá trị này bằng số lượng các gói tin UDP trong 1 giây mà băng thông cho phép, nội dung chính sách an ninh gồm địa chỉ IP của Server sẽ mô tả địa chỉ máy chủ cần kiểm soát, ngưỡng phát hiện tấn công và lượng băng thông dành cho UDP sẽ kiểm soát sự bất thường của các gói tin.
2) Phát hiện gói tin IP bất thường: Số lượng gói tin UDP đến Server có thể kiểm soát nhờ các Router trong mạng NGN. Tấn công DoS được phát hiện khi khi số lượng các gói tin UDP trong một giây vượt quá số lượng gói tin đã được thiết lập trong chính sách bảo mật riêng. Việc kiểm tra được thực hiện trên kiểu gói tin UDP, địa chỉ IP và số hiệu cổng đích.
3) Truyền thông báo cho các thiết bị: Sau khi phát hiện bị tấn công DoS, Router đó sẽ gửi cảnh báo đến tất cả các Router khác thông qua giao thức SIP. Giao thức SIP này được xem là phần mở rộng của chính sách an ninh riêng. Các thông của truyền đi bao gồm kiểu gói tin tấn công, địa chỉ IP, số hiệu cổng của máy bị tấn công và độ trễ yêu cầu. Các thông tin này được sử dụng để đánh dấu các gói tin. Thời gian trễ này được sử dụng để điều khiển đường truyền.
4) Đánh dấu các gói tin: các nút Router trong mạng NGN sẽ kiểm tra tất cả thông tin của các gói tin dựa vào thông báo được gửi đến qua giao thức SIP. Các gói tin trước khi thông qua sẽ được ghi lại nhãn thời gian trong tiêu đề mở rộng của gói tin IP (Hiện nay giao thức SIP chưa có chức năng này và đang được đề xuất xây dựng). Trong trường hợp các gói tin IP có kích thước lớn thì ta tiến hành phân mảnh trước khi ghi nhãn thời gian lên các phân mảnh đó.
Quá trình kiểm soát được thực hiện bằng lượng băng thông tối thiểu cho phép chuyển tiếp các gói tin UDP từ mạng NGN đến mạng LAN, dựa vào đó ta sẽ ngăn chặn được các tấn công DoS bằng cách hạn chế số lượng gói tin UDP như Hình 3.1.
Hình 3.1 – Quá trình điều khiển đường truyền
Việc điều khiển đường truyền trong mạng NGN sẽ thực hiện dựa trên thời gian trễ được đánh dấu trong các gói tin IP được chuyển tiếp lặp lại quay vòng tại đầu vào các nút Router. Khi nhận một gói tin IP, nhãn thời gian được đánh dấu sẽ được so sánh với thời gian hiện thời để đảm bảo rằng thời gian trễ yêu cầu đã được thêm vào. Phương pháp đề xuất sẽ làm giảm số lượng các gói tin trong một đơn vị thời gian bằng cách kiểm soát độ trễ của các gói tin. Đồng nghĩa với việc các cuộc tấn công DoS sẽ được kiểm soát nhờ việc tăng độ trễ của các gói tin tấn công. Tuy nhiên, các gói tin hợp lệ từ phía người dùng cũng bị ảnh hưởng bởi độ trễ nhưng là rất nhỏ.
20
Kiến trúc mạng mô phỏng là sự kết hợp của mạng LAN, NGN và Internet được thể hiện trong Hình 3.2. Trong đó, chúng ta sử dụng 2 nguồn phát sinh gói tin UDP chính từ Internet. Một nguồn được sinh ra bởi 2 người dùng là A và B , nguồn còn lại là do kẻ tấn công DoS tạo ra. Giả sử rằng tất cả các gói tin UDP đều được truyền qua mạng NGN từ mạng Internet đến mạng LAN, băng thông truy cập được truyền giữa mạng NGN và LAN là 10 Mbps, băng thông giữa mạng Internet và NGN là lớn hơn 10 Mbps, băng thông giữa các Router điều khiển được với các Router lõi là 100 Mbps.
Hình 3.2 – Kiến trúc mạng mô phỏng DDoS
Để kiểm chứng, tác giả đã tiến hành thực nghiệm mô phỏng trên phần mềm NS2 phiên bản 2.33 [2]. Cấu trúc mạng mô phỏng tấn công với 20 nút (ni , i = 1..20) như sau: Nút n1, n2, n3, n4, n5 biểu diễn các Router lõi ; Nút n6, n7, n8, n9, n10 biểu diễn các nút Router có thể điều khiển được. Nút n12, n13, n14, n15, n16 biểu diễn người dùng. Nút n17, n18, n19, n20 lần lượt là các máy chủ NTP , HTTP , DNS1, DNS2. Nút n11 là kẻ tấn công, đích tấn công là n19, n20. Kịch bản 1 là nút n11 tấn công vào n19, các người dùng n12, n14 cùng lúc truy cập đến n19. Kịch bản 2 là nút n11 tấn công đồng thời vào n19 và n20 ; người dùng n12, n14 cùng gửi gói tin đến n19 ; người dùng n13, n15, n16 gửi gói tin đến n20. Tham số chi tiết cho các đối tượng thực nghiệm được thể hiện với tốc độ truyền không đổi, chính sách bảo mật được thiết lập bảo vệ đối với n19 và n20 được thể hiện trong [3] (danh mục công trình).
Kịch bản mô phỏng được thực hiện với thời gian tấn công kéo dài 30 giây, thời điểm bắt đầu tấn công là giây thứ 5. Thông số đánh giá là tỷ lệ băng thông truy cập đường truyền ở mức thông thường và khi được điều khiển với chính sách an ninh riêng. Trong kịch bản 1, thời gian từ 0-5 giây, lưu lượng gói tin UDP trong mạng của cả người dùng thông thường và kẻ tấn công DoS là 1.15 Mbps. Sau khi kẻ tấn công thực hiện chiếm toàn bộ băng thông đường truyền từ giây thứ 5 sẽ thì gây ra tắc nghẽn tạm thời. Khi áp dụng phương pháp kiểm soát sau 5 giây khi phát hiện tấn công DoS thì băng thông của mạng bị tấn công DoS giảm xuống gần với băng thông của người dùng thông thường và nằm dưới ngưỡng cho phép 1.75 Mbps như Hình 3.3(a).
Tương tự với kịch bản 2, trong thời gian từ 0-5 giây, lưu lượng mạng của cả người dùng thông thường và kẻ tấn công DoS đều chiếm 50% bằng thông. Sau đó, mô phỏng kẻ tấn công thực hiện chiếm toàn bộ băng thông đường truyền 10 Mbps từ giây thứ 5. Khi áp dụng phương pháp kiểm soát dựa trên thời gian trễ sau 5
21
Hình 3.3 – Kết quả kiểm soát băng thông gói tin UDP của kịch bản 1 và 2
giây khi phát hiện tấn công DoS thì băng thông của mạng bị tấn công DoS giảm xuống gần với băng thông của người dùng thông thường như Hình 3.3(b).
Kết quả mô phỏng cho thấy tắc nghẽn tạm thời gây ra bởi cuộc tấn công DoS. Nhưng sau khi phương pháp điều khiển cuộc tấn công DoS được thực hiện, băng thông giao tiếp của người sử dụng thường xuyên được bảo đảm và những người sử dụng có thể giao tiếp mà không cần bất kỳ ảnh hưởng của các cuộc tấn công DoS. Điều này cũng khẳng định rằng dòng lưu lượng trong nội bộ mạng NGN không bị ảnh hưởng bởi các gói tin tấn công DoS đã được kiểm soát tại các cổng vào của Router. Các biện pháp phòng chống tấn công DoS hiện đang được áp dụng trên mạng là Moving Firewall [4, 5]. Sự khác biệt giữa đề xuất trong bài báo này và nghiên cứu trước đó thể hiện ở các điểm sau:
- Phương pháp kiểm soát tấn công của DoS sử dụng thiết bị Moving Firewall điều khiển băng thông được còn giải pháp bài báo đưa ra là điều khiển độ trễ tại các nút Router.
- Các gói tin tấn công DoS được phát hiện tại các nút Router chỉ bị trì hoãn chứ không bị loại bỏ như như dùng Moving Firewall nên không làm mất các gói tin của người dùng hợp lệ mà chỉ làm chậm lại, nhưng thời gian trễ đó là không đáng kể.
- Giải pháp đề xuất chỉ sử dụng các nút Router điều khiển được tại các cổng mạng trong khi phương pháp Moving Firewall thiết lập trên toàn bộ mạng giống như các cảm biến.
Từ sự khác biệt trên, giải pháp được đề xuất có thể được dự kiến sẽ ngăn
chặn các cuộc tấn công DoS hiệu quả hơn so với các biện pháp trước.
3.4 Kết luận chương 3
Trong chương này, luận án đã phân tích những thách thức và khó khăn trong việc đảm bảo an ninh các dịch vụ trong mạng NGN. Đặc biệt là những khó khăn khi ngăn chặn các cuộc tấn công DoS đối với các máy chủ dịch vụ, đây thực sự là một vấn đề nan giải. Từ những phân tích đó, tác giả đề xuất biện pháp phòng chống tấn công DoS trong mạng NGN dựa trên chính sách an ninh riêng được thiết lập trên các Router có thể điều khiển được. Hiệu quả của biện pháp đề xuất đã được mô phỏng trên NS-2 và so sánh đánh giá với những hướng tiếp cận trước đó. Kết quả thực nghiệm cho thấy giải pháp đề xuất có thể phát hiện và kiểm soát các đợt tấn công DoS dựa trên UDP khá hiệu quả.
22
Kết luận
Trong luận án, tác giả đã trình bày các kết quả nghiên cứu về qui hoạch, phát triển, nâng cấp và mở rộng cơ sở hạ tầng các mạng hiện có lên mạng thế hệ mới nhằm tối ưu vị trí các thiết bị, kết nối và dung lượng. Đặc biệt là tập trung đến việc quản lý, phân bố tài nguyên tập trung cho các lớp dịch vụ và các luồng đa phương tiện. Đây là những vấn đề ngày càng trở nên cấp thiết đối với các nhà cung cấp dịch vụ mạng do sự phát triển không ngừng các lớp ứng dụng mới hội tụ trên nền IP trong mạng NGN. Những kết quả nghiên cứu này vừa có tính tổng hợp, hệ thống hóa vừa mang tính đề xuất, phát triển, áp dụng và kiểm chứng những giải thuật tiến hóa để giải các bài toán tối ưu đơn mục tiêu, đa mục tiêu khó nhiều ràng buộc hiện chưa có thuật toán hiệu quả để giải quyết bằng cách tìm ra các phương án gần tối ưu hiệu quả nhanh trong thời gian tuyến tính.
1. Các đóng góp của luận án
Những kết quả nghiên cứu của luận án có ý nghĩa trong việc bổ sung và hoàn thiện các giải pháp tối ưu qui hoạch và cấp phát tài nguyên hiệu quả cho các lớp dịch vụ đảm bảo yêu cầu về QoS. Cụ thể, luận án đã đóng góp 4 kết quả chính như sau:
(cid:4) Đề xuất thuật toán ACO tối ưu mở dung lượng mạng không dây kế thừa cơ sở hạ tầng sẵn có với mục tiêu hướng đến là tối thiểu chi phí vận hành, cài đặt, nâng cấp và chi phí xây mới các thành phần mạng để đảm bảo nhu cầu về lưu lượng trên toàn hệ thống. Đánh giá được ảnh hưởng của số lượng kiến và số vòng lặp đến thời gian thực thi và hàm mục tiêu của thuật toán.
(cid:4) Đề xuất thuật toán MMAS tối ưu cấp phát tài nguyên cho các lớp dịch vụ có xét đến yêu cầu về QoS có thể áp dụng mềm dẻo khi số lớp dịch vụ lớn. Khắc phục được hạn chế của các phương pháp tất định sử dụng tính chất giải tích của hàm mục tiêu và ràng buộc không hiệu quả khi số lượng lớp dịch vụ tăng. Đánh giá được sự ảnh hưởng của các tham số trong lớp dịch vụ đến hàm mục tiêu.
(cid:4) Đề xuất thuật toán MMAS tối ưu tài nguyên cho các luồng đa phương tiện đảm bảo yêu cầu về QoS của các ứng dụng đa phương tiện có thể áp dụng trên nhiều luồng dịch vụ đa phương tiện với số lượng ràng buộc lớn. Mục tiêu hướng đến là xây dựng cấu hình cấp phát tài nguyên mạng cho người dùng thỏa mãn các ràng buộc đã cam kết theo trọng số có thể dùng để biểu diễn tương đối mức độ đáp ứng dịch vụ cho một luồng dữ liệu với mục tiêu cực đại hàm chi phí thu được.
23
(cid:4) Đề xuất giải pháp phòng chống tấn công từ chối dịch vụ phân tán trong mạng NGN dựa trên chính sách an ninh bảo mật riêng được thiết lập trên các Router có thể điều khiển được. Các gói tin tấn công được phát hiện tại các nút Router chỉ bị trì hoãn chứ không bị loại bỏ nên không làm mất các gói tin của người dùng hợp lệ mà chỉ làm chậm lại, nhưng thời gian trễ đó là không đáng kể. Kết quả thực nghiệm cho thấy giải pháp đề xuất có thể phát hiện và kiểm soát hiệu quả các đợt tấn công.
Ưu điểm của các thuật toán đề xuất là sự hội tụ nhanh với các qui tắc heuristic kết hợp học tăng cường thông qua thông tin vết mùi cho phép từng bước thu hẹp không gian tìm kiếm mà vẫn không loại bỏ các lời giải tốt để nâng cao chất lượng lời giải. Tuy nhiên, các quy tắc này không phải luôn có được và rất khó có thể can thiệp để thay đổi chất lượng. Do vậy, trong các bài toán chúng ta cần quan tâm tới cách cập nhật mùi để nâng cao chất lượng thuật toán. Hơn nữa, việc lựa chọn và thiết lập các tham số trong thực thi thuật toán tối ưu đàn kiến cũng rất quan trọng bởi nó sẽ ảnh hưởng đến sự hiệu quả của thuật toán. Qua thực nghiệm, luận án đã lựa chọn được bộ tham số phù hợp và hiệu quả để thu được chất lượng lời giải tốt nhất đối với từng bài toán.
Các kết quả của luận án đã được công bố trong 4 báo cáo tại các Hội nghị quốc tế, 3 bài báo trên các tạp chí quốc tế, 2 bài báo trong Kỷ yếu Hội thảo Quốc gia Một số vấn đề chọn lọc của Công nghệ thông tin và Truyền thông.
2. Hướng phát triển
Trong luận án này, tác giả đã đề xuất các thuật toán Meta-Heurisctic để tìm phương án tối ưu trong thời gian tuyến tính giải quyết các bài toán tối ưu trong mạng NGN. Công việc tiếp theo tác giả hướng đến là:
(cid:4) Mô hình hóa chi tiết các bài toán tối ưu định vị và mở rộng dung lượng mạng không dây sát với thực tế cho phép thực thi và áp dụng trên các dữ liệu thực nhằm giải quyết bài toán qui hoạch lại hệ thống trạm BTS và phát triển hạ tầng mạng viễn thông hiện nay. Tiếp tục cải tiến và thử nghiệm thêm các phương pháp cập nhật vết mùi mới nhằm nâng cao hiệu quả và chất lượng của lời giải.
(cid:4) Nghiên cứu và đề xuất các giải pháp đảm bảo an ninh các dịch vụ trên mạng NGN bởi vì bảo mật là một tham số mới nhưng rất quan trọng của QoS. Đặc biệt là các mô hình và kỹ thuật mới phòng chống các kiểu tấn công từ chối dịch vụ- mối đe dọa lớn làm và gây ảnh hưởng nghiêm trọng đến chất lượng dịch vụ được cung cấp.
(cid:4) Nghiên cứu mở rộng các bài toán định vị tài nguyên hỗ trợ QoS cho các dịch vụ trong môi trường tập trung và phân tán trên mạng có tính tương tác cao như trong lý thuyết trò chơi và các mạng xã hội. Nghiên cứu các kỹ thuật định tuyến mạng đáp ứng yêu cầu về chất lượng dịch vụ, giải pháp điều khiển luồng tránh tắc nghẽn và phân chia tài nguyên cho các luồng tin với các ứng dụng khác nhau một cách hợp lý tránh để các ứng dụng chiếm nhiều tài nguyên gây suy giảm QoS cung cấp.
24
Danh mục công trình khoa học
1. Dac-Nhuong Le, Evaluation of Pheromone Update in Min-Max Ant Sys- tem Algorithm to Optimizing QoS for Multimedia Services in NGNs, in pro- ceeding of the 49th International Conference on Emerging ICT for Bridging Future (CSI 2014), Hyderabad, India, Dec 12–14, 2014. Advances in Intelli- gent System and Computing, Vol.338, pp.9-17, Springer (ISI Proceeding). 2. Dac-Nhuong Le, MMAS Algorithm Applied to Optimal Resource Alloca- tion to Support QoS Requirements in NGNs, Proceeding of the 8th Interna- tional Wireless Internet Conference, Symposium on Wireless and Vehicular Communication (WICON 2014), Lisbon, Portugal, November 13–14, 2014. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, pp.212-217, Springer (ISI Proceeding).
3. Lê Đắc Nhường, Nguyễn Gia Như, Lê Trọng Vĩnh. Giải pháp phòng chống tấn công DDoS dựa trên chính sách bảo mật trong mạng thế hệ mới, Kỷ yếu Hội thảo quốc gia Một số vấn đề chọn lọc của Công nghệ thông tin và Truyền thông lần thứ 16, Đà Nẵng, Tr.95-102, Nxb KH&KT Hà Nội, 2013.
4. Dac-Nhuong Le, Nhu Gia Nguyen, Dac Binh Ha, Vinh Trong Le. A new genetic algorithm applied to objectives optimal of upgrading infrastructure in NGWN, Proceeding of International conference wireless communication, networking, and mobile computing (WICOM 2013), Journal of Communica- tion Network, Vol.5(3)B, pp.223-231, Beijing, China, September 25-26, 2013. 5. Dac-Nhuong Le, Son Hong Ngo, Vinh Trong Le. ACO algorithm applied to multi-objectives Optimal of Capacity Expansion in NGWN, International Journal of Wireless and Microwave Technologies, Vol.3(1), pp.37-49, 2013.
6. Lê Đắc Nhường, Nguyễn Gia Như, Lê Trọng Vĩnh. Tối ưu phân bố tài nguyên cho các lớp dịch vụ đáp ứng yêu cầu về QoS trong mạng NGN sử dụng thuật toán tối ưu đàn kiến, Kỷ yếu Hội thảo quốc gia Một số vấn đề chọn lọc của CNTT&TT lần thứ 17, Đăklăk 30-31/10/2014.
7. Dac-Nhuong Le. Optimizing Resource Allocation to Support QoS Requi- rements in Next Generation Networks using ACO Algorithm, Internatio- nal Journal of Computer Science and Information Technology & Security, Vol.2(5), pp.931-938, 2012.
8. Dac-Nhuong Le. DDoS Attack defense in Next Generation Networks using Private Security Policy, International Journal of Information & Network Security, Vol.3(3), pp.205-216, 2014.
9. Dac-Nhuong Le, Performance evaluation of heuristic algorithms for op- timal location of controllers in wireless networks, in proceeding of the In- ternational Conference on Information systems Design and Intelligent Ap- plications (INDIA 2015), West Bengal, India, Jan 8-9, 2015. Advances in Intelligent System and Computing, Vol.339 Springer (ISI Proceeding).
