Luận án Tiến sĩ Công nghệ thông tin: Nghiên cứu nâng cao hiệu năng hoạt động của mạng ngang hàng có cấu trúc

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

Thêm vào BST

Báo xấu

42
lượt xem 5
download

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

Luận án phân tích các đặc điểm của mạng ngang hàng có cấu trúc ảnh hướng đến cân bằng tải xử lý truy vấn, khả năng định tuyến của các nút và tính sẵn sàng của dữ liệu trong mạng. Trên có sở đó, luận án đề xuất một số thuật toán nâng cao hiệu năng hoạt động của mạng ngang hàng có cấu trúc.

Chủ đề:

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

Lưu

Nội dung Text: Luận án Tiến sĩ Công nghệ thông tin: Nghiên cứu nâng cao hiệu năng hoạt động của mạng ngang hàng có cấu trúc

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN ĐÌNH NGHĨA NGHIÊN CỨU NÂNG CAO HIỆU NĂNG HOẠT ĐỘNG CỦA MẠNG NGANG HÀNG CÓ CẤU TRÚC LUẬN ÁN TIẾN SĨ NGÀNH CÔNG NGHỆ THÔNG TIN Hà Nội - 2019
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN ĐÌNH NGHĨA NGHIÊN CỨU NÂNG CAO HIỆU NĂNG HOẠT ĐỘNG CỦA MẠNG NGANG HÀNG CÓ CẤU TRÚC Chuyên ngành: Mạng máy tính và truyền dữ liệu Mã số: 9480102.01 LUẬN ÁN TIẾN SĨ NGÀNH CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. TS Nguyễn Hoài Sơn 2. PGS.TS Hồ Sỹ Đàm Hà Nội - 2019
MỤC LỤC MỞ ĐẦU .................................................................................................. 1 1. Đặt vấn đề ......................................................................................... 1 2. Mục tiêu của luận án ......................................................................... 8 3. Phạm vi nghiên cứu, đối tượng nghiên cứu ...................................... 8 4. Phương pháp nghiên cứu .................................................................. 9 5. Đóng góp của luận án........................................................................ 9 6. Cấu trúc của luận án ........................................................................ 10 Chương 1. KIẾN THỨC NỀN TẢNG ................................................ 13 1.1. Mạng ngang hàng ......................................................................... 13 1.2. Ứng dụng mạng ngang hàng ........................................................ 15 1.2.1. Phân phối nội dung dựa trên mạng ngang hàng .................. 15 1.2.2. Truyền thông dựa trên mạng ngang hàng ............................ 16 1.2.3. Xử lý và tính toán phân tán dựa trên mạng ngang hàng ...... 16 1.2.4. Cộng tác dựa trên mạng ngang hàng ................................... 17 1.2.5. Hạ tầng công nghiệp/nền tảng dựa trên mạng ngang hàng . 17 1.2.6. Các hệ thống cơ sở dữ liệu và tìm kiếm dựa trên mạng ngang hàng ......................................................................................................... 18 1.2.7. Các ứng dụng khác ............................................................... 18 1.3. Phân loại mạng ngang hàng ......................................................... 18 1.3.1. Phân loại theo mức độ phân tán ........................................... 19 1.3.2. Phân loại theo cấu trúc mạng ngang hàng ........................... 22 1.4. Mạng ngang hàng có cấu trúc ...................................................... 24 1.4.1. Bảng băm phân tán ............................................................... 25 1.4.2. Mạng ngang hàng Chord ...................................................... 28 1.4.3. Một số giao thức mạng ngang hàng có cấu trúc khác .......... 36 i
1.5. Kết luận ........................................................................................ 37 Chương 2. CÂN BẰNG TẢI TRONG MẠNG NGANG HÀNG CÓ CẤU TRÚC .................................................................................................... 38 2.1. Đặt vấn đề .................................................................................... 38 2.2. Các nghiên cứu liên quan ............................................................. 41 2.2.1. Cân bằng tải theo ngưỡng .................................................... 41 2.2.2. Cân bằng tải dựa trên server ảo. .......................................... 43 2.2.4. So sánh các thuật toán cân bằng tải ..................................... 45 2.3. Cải tiến thuật toán cân bằng tải theo ngưỡng .............................. 46 2.3.1. Một số khái niệm ................................................................... 46 2.3.2. Thuật toán ThresholdPlus ..................................................... 48 2.4. Đánh giá thuật toán ...................................................................... 56 2.4.1. Phương pháp đánh giá .......................................................... 56 2.4.2. Các kết quả mô phỏng........................................................... 57 2.5. Kết luận ........................................................................................ 63 Chương 3. ĐIỀU KHIỂN TẮC NGHẼN TRONG MẠNG NGANG HÀNG CÓ CẤU TRÚC ................................................................................ 65 3.1. Đặt vấn đề .................................................................................... 66 3.2. Các nghiên cứu liên quan ............................................................. 68 3.3. Điều khiển tắc nghẽn bằng thay đổi bảng định tuyến .................. 73 3.4. Đánh giá thuật toán ...................................................................... 82 3.4.1. Phương pháp đánh giá .......................................................... 82 3.4.2. Các kết quả mô phỏng........................................................... 83 3.5. Kết luận ........................................................................................ 94 Chương 4. SAO LƯU DỮ LIỆU TRONG MẠNG MẠNG NGANG HÀNG CÓ CẤU TRÚC ................................................................................ 95 4.1. Đặt vấn đề .................................................................................... 95 ii
4.2. Các nghiên cứu liên quan ............................................................. 97 4.3. Sao lưu dữ liệu dựa trên phân cụm trong mạng P2P ................. 102 4.3.1 Tổng quan ............................................................................ 102 4.3.2 Quản lý thông tin cụm .......................................................... 103 4.3.3. Sao lưu và truy vấn dữ liệu ................................................. 106 4.3.4. Khôi phục tệp tin ................................................................. 108 4.3.5. Xây dựng cụm...................................................................... 111 4.3.6. Đảm bảo tính cục bộ và cân bằng tải ................................. 116 4.4. Đánh giá thuật toán .................................................................... 118 4.4.1. Phương pháp đánh giá ........................................................ 118 4.4.2. Các kết quả mô phỏng......................................................... 120 4.5. Kết luận ...................................................................................... 132 KẾT LUẬN .......................................................................................... 134 1. Các kết quả đã đạt được ................................................................ 134 2. Những hạn chế và hướng nghiên cứu tiếp theo ............................ 136 DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN .............................................................................. 137 TÀI LIỆU THAM KHẢO .................................................................. 138 iii
Danh sách hình vẽ Hình 1.1. Phân loại mạng ngang hàng .................................................... 19 Hình 1.2. Phân loại mạng ngang hàng theo mức độ phân tán ................ 20 Hình 1.3. Ánh xạ dữ liệu vào mạng DHT ............................................... 26 Hình 1.4. Mạng phủ DHT với 4 nút trong mạng .................................... 27 Hình 1.5. Vòng Chord với độ dài không gian khóa là 6 bit.................... 30 Hình 1.6. Tìm kiếm đơn giản trên Chord................................................ 31 Hình 1.7. Bảng finger của nút n8............................................................. 32 Hình 1.8. Giả mã của phương pháp tìm kiếm nâng cao ......................... 33 Hình 1.9. Quá trình tìm kiếm khóa k54 trên nút n8 .................................. 33 Hình 2.1. Chuyển tải giữa các nút láng giềng. ........................................ 41 Hình 2.2. Khả năng và tải làm việc của một nút..................................... 48 Hình 2.3. Các nút nhẹ tải thông báo thông tin cho thư mục ................... 50 Hình 2.4. Nút n1 thực hiện cân bằng tải, nút láng giềng n5 nhận tải hộ nút n1 bằng cách dịch chuyển định danh về phía n1 .............................................. 51 Hình 2.5. Nút n1 thực hiện cân bằng tải, nút n1 chia tải cho nút láng giềng n2 bằng cách dịch chuyển định danh của n1 về phía n5. .................................. 52 Hình 2.6. Di chuyển định danh để thực hiện cân bằng tải ...................... 53 Hình 2.7 Giả mã của thuật toán ThresholdPlus ...................................... 54 Hình 2.8. Thời gian sống trung bình của một nút thay đổi, các câu truy vấn thực hiện với phân bố Zipf và Uniform. .................................................. 59 Hình 2.9. Số câu truy vấn đặt vào một nút thay đổi, truy vấn được phân bố ở dạng Zipf và Uniform. ............................................................................ 60 Hình 2.10. Truy vấn đặt vào các nút ở dạng phân bố Zipf ..................... 61 Hình 2.11. Chi phí của các thuật toán cân bằng tải ................................ 62 Hình 3.1. Giả mã thuật toán xử lý tắc nghẽn tại nút n ............................ 76 Hình 3.2. Giả mã thuật toán xử lý hết tắc nghẽn tại nút n ...................... 79 iv
Hình 3.3. Truy vấn thông thường trong mạng Chord (m=6) .................. 80 Hình 3.4. Tỷ lệ truy vấn thành công khi thay đổi thời gian sống trung bình của nút ..................................................................................................... 84 Hình 3.5. Tỷ lệ thành công với số truy vấn đặt vào mỗi nút thay đổi .... 86 Hình 3.6. Tỷ lệ thành công của các truy vấn khi thay đổi ngưỡng mềm 87 Hình 3.7. Ảnh hưởng của tham số Zipf đến tỷ lệ thành công của truy vấn ......................................................................................................................... 88 Hình 3.8. Ảnh hưởng của số truy vấn đặt vào một nút đến số bước chuyển tiếp truy vấn ........................................................................................ 90 Hình 3.9. Ảnh hưởng của thời gian sống trung bình đến số bước chuyển tiếp truy vấn..................................................................................................... 91 Hình 3.10. Ảnh hưởng truy vấn đặt vào nút đến số thông báo tắc nghẽn ......................................................................................................................... 92 Hình 3.11. Ảnh hưởng của số lượng truy vấn đặt vào nút đến số thông báo hết tắc nghẽn ............................................................................................. 93 Hình 4.1. Phạm vi không gian khóa của các cụm ................................. 103 Hình 4.2. Thông báo cập nhật trong cụm có không gian khóa là [𝐾𝑓𝑑, 𝐾𝑙𝑑] ..................................................................................................... 104 Hình 4.3. Ví dụ về sao lưu một tệp dữ liệu ........................................... 106 Hình 4.4. Giả mã sao lưu dữ liệu tại nút s ............................................ 107 Hình 4.5. Giả mã của thuật toán khôi phục dữ liệu tại nút quản lý khóa ....................................................................................................................... 109 Hình 4.6. Thủ tục truy vấn và sao lưu tệp tin ....................................... 110 Hình 4.7. Đoạn giả mã thủ tục tách một cụm thành cụm B và C ......... 114 Hình 4.8. Giả mã thủ tục nhập cụm hàng xóm A vào cụm B thành cụm C ....................................................................................................................... 115 Hình 4.9. Giả mã thủ tục tham gia mạng của một nút .......................... 117 Hình 4.10. Ví dụ về mô hình Transit stub ............................................ 119 v
Hình 4.11. Tỷ lệ truy vấn thành công với dữ liệu phân phối vào các nút so với khả năng lưu trữ của một nút.............................................................. 123 Hình 4.12. Tỷ lệ truy vấn thành công với thời gian sống trung bình của một nút thay đổi............................................................................................. 125 Hình 4.13. Tỷ lệ truy vấn thành công với số lượng các nút ra/vào trong mạng thay đổi ................................................................................................ 126 Hình 4.14. Tỷ lệ truy vấn thành công với số lượng vị trí thử khác nhau của một nút khi tham gia mạng ..................................................................... 127 Hình 4.15. Chi phí duy trì với thời gian sống trung bình của các nút khác nhau ............................................................................................................... 128 Hình 4.16. Chi phí duy trì với số nút ra/vào khác nhau ........................ 129 Hình 4.17. Ảnh hưởng của các tham số sao lưu đối đến tỷ lệ truy vấn thành công khi thời gian sống trung bình của một nút thay đổi ................... 130 Hình 4.18. Ảnh hưởng của các tham số truy vấn đến chi phí duy trì khi thời gian sống của một nút thay đổi .............................................................. 131 Hình 4.19. Ảnh hưởng của các tham số sao lưu đến tỷ lệ thành công của các truy vấn khi số lượng các tệp tin phân phối vào các nút thay đổi so với khả năng của một nút .................................................................................... 132 vi
Danh sách bảng Bảng 1.1 Phân loại các hệ thống mạng ngang hàng ............................... 24 Bảng 2.1. So sánh các thuật toán cân bằng tải ........................................ 46 Bảng 3.1. So sánh các thuật toán điều khiển tắc nghẽn .......................... 73 Bảng 3.2. Bảng định tuyến ban đầu của nút ni........................................ 77 Bảng 3.3. Bảng tìm đường của nút ni sau khi thay đổi ........................... 78 Bảng 4.1. Bảng so sánh các thuật toán sao lưu dữ liệu......................... 101 vii
Thuật ngữ và từ viết tắt Từ viết tắt Từ gốc Giải nghĩa ACK Acknowledge receipt of a packet BPCC Back-Pressure Congestion Control CAN Content Addressable Network Giao thức mạng ngang hàng có cấu trúc CCLBR Congestion Control-Based Load Balanced Routing CPU Central Processing Unit Bộ xử lý trung tâm CSCC Credit System Congestion Control DHT Distributed Hash Table Bảng băm phân tán HTTP Hypertext Transfer Protocol Giao thức truyền siêu văn bản ID Identification Định danh IM Instant Messaging Thông điệp tức thì IP Internet Protocol Giao thức Internet IPTV Internet Protocol Television Truyền hình Internet JXTA Juxtapose P2P Peer to peer Ngang hàng QoS Quality of Service Chất lượng dịch vụ REC Replicated Easure Code Mã xóa RTT Round-Trip Time SHA Secure Hash Algorithm Giải thuật băm an toàn TCP Transmission Control Protocol TTL Time-to-live Thời gian sống VoIP Voice over Internet Protocol VoD Video on demand Video theo yêu cầu XML Extensible MarkupLanguage Ngôn ngữ đánh dấu mở rộng viii
Lời cam đoan Tôi xin cam đoan luận án “Nghiên cứu nâng cao hiệu năng hoạt động của mạng ngang hàng có cấu trúc” là do tôi thực hiện dưới sự hướng dẫn của TS Nguyễn Hoài Sơn và PGS.TS Hồ Sỹ Đàm. Luận án không chứa bất kỳ nội dung nào được sao chép từ các công trình đã được người khác công bố. Các tài liệu trích dẫn là trung thực và được chỉ rõ nguồn gốc. Tôi xin hoàn toàn chịu trách nhiệm về lời cam đoan trên. ix
Lời cảm ơn Nghiên cứu sinh Nguyễn Đình Nghĩa xin được bày tỏ lòng biết ơn sâu sắc đến các thầy hướng dẫn khoa học là TS Nguyễn Hoài Sơn và PGS.TS Hồ Sỹ Đàm những người đã hướng dẫn tận tình, chỉ bảo, khích lệ và động viên tôi hoàn thành luận án này. Nghiên cứu sinh xin chân thành cảm ơn ban lãnh đạo Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội đã tạo môi trường thuận lợi và điều kiện nghiên cứu tốt cho nghiên cứu sinh trong suốt quá trình làm nghiên cứu. Đồng thời, nghiên cứu sinh cũng xin được cảm ơn các thầy, cô Bộ môn Truyền thông và Mạng máy tính; các thầy, cô Khoa Công nghệ Thông tin Trường Đại học Công nghệ; các chuyên gia, các bạn đồng nghiệp đã hỗ trợ nghiên cứu sinh trong suốt quá trình học tập, nghiên cứu và bảo vệ luận án, các nghiên cứu sinh, học viên cao học và sinh viên đã tham gia seminar của Bộ môn Truyền thông và Mạng máy tính. Cuối cùng, tôi xin chân thành cảm ơn những người thân trong gia đình cùng toàn thể bạn bè đã luôn giúp đỡ, động viên tôi những lúc gặp phải khó khăn trong suốt quá trình học tập và nghiên cứu. x
MỞ ĐẦU 1. Đặt vấn đề Internet là một hệ thống thông tin toàn cầu được phát triển từ những năm giữa thế kỷ 20. Ban đầu phạm vi của mạng còn hạn chế, các dịch vụ triển khai hết sức đơn giản. Cho đến năm 1980, với sự ra đời của giao thức mạng TCP/IP, đánh dấu bước phát triển mới để trao đổi thông tin giữa người dùng máy tính trên toàn thế giới. Giao thức TCP/IP là một giao thức chuẩn được cài đặt trên tất cả các máy tính kết nối với mạng Internet giúp các máy tính kết nối và trao đổi dữ liệu với nhau một cách dễ dàng hơn. Với khả năng kết nối mở như vậy, Internet đã trở thành một mạng lớn nhất trên thế giới với số lượng các máy tính tham gia vào mạng lên đến 4,4 tỷ người dùng tính đến tháng 6/2019 [77]. Cũng từ đó, các dịch vụ, ứng dụng trên Internet không ngừng phát triển và xuất hiện trong các lĩnh vực thương mại, chính trị, quân sự, nghiên cứu, giáo dục, văn hoá, xã hội, v.v. Ban đầu các ứng dụng trên mạng Internet được phát triển theo mô hình Client/Server (hay còn được gọi là mạng Client/Server). Trong mạng Client/Server gồm hai thành phần đó là máy chủ và máy khách. Máy khách là nơi gửi các yêu cầu của người dùng tới máy chủ. Máy chủ là nơi xử lý và gửi kết quả cho máy khách. Các ứng dụng, dịch vụ tiểu biểu cho mô hình Client/Server có thể kể đến như: File Server, Print Server, Applcation Server, Mail Server, Web Server, Database Server, Communication Server, v.v. Mạng Client/Server có nhiều ưu điểm như: tài nguyên được quản lý tập trung, dễ chia sẻ, dễ bảo mật, tốc độ xử lý nhanh. Bên cạnh đó nó cũng tồn tại không ít nhược điểm như: khả năng mở rộng mạng kém, xảy ra hiện tượng nghẽn cổ chai khi số người dùng tăng lên, không tận dụng được tài nguyên chia sẻ của người dùng (tệp tin, sức mạnh CPU, bộ nhớ lưu trữ, băng thông, v.v.) tham gia mạng, nhất là trong thời đại 1
ngày nay khi mà số người dùng Internet lớn, tài nguyên mạng nhiều, yêu cầu xử lý đối với các bài toán lớn, v.v. Trong bối cảnh đó, các mạng ngang hàng (P2P) đóng một vai trò hết sức quan trọng để truyền tải nội dung đa phương tiện và mở rộng phạm vi mạng đến các người dùng khác nhau, khắc phục được các nhược điểm của mô hình Client/Server. Mạng ngang hàng là một kiến trúc máy tính phân tán xây dựng trên mạng Internet, cho phép các máy tính riêng lẻ (hay còn gọi là các nút) trao đổi thông tin và dịch vụ trực tiếp với nhau không cần qua máy chủ trung tâm. Mỗi nút trong mạng ngang hàng hoạt động với chức năng như một máy chủ và một máy khách, sử dụng dịch vụ của các nút tham gia mạng đồng thời cung cấp dịch vụ cho các nút khác [1]. Các nút trong mạng ngang hàng trao đổi trực tiếp với các nút láng giềng có liên kết với nó để gửi và phục vụ các yêu cầu. Trong mạng ngang hàng, không có thực thể trung tâm kiểm soát, tổ chức, quản lý hoặc duy trì toàn bộ hệ thống. Đã có nhiều ứng dụng được phát triển trên nền tảng công nghệ mạng mạng ngang hàng bao gồm các ứng dụng chia sẻ tệp tin (như: uTorrent, BitTorrent, BearShare, eMule, v.v.), các ứng dụng tính toán lưới, các ứng dụng truyền thông như Skype, WhatsApp, Lync, Google Talk SETI @ home, IPTV, Video streaming, v.v. Các ứng dụng này cho phép người dùng chia sẻ, tìm kiếm và thu thập các tệp tin tệp tin hình ảnh, âm thanh, video, tệp tin đa phương tiện khác; trao đổi thông tin trực tuyến, xem truyền hình, v.v. đồng thời có thể sử dụng sức mạnh của các máy tính tham gia mạng ngang hàng để giải quyết các bài toán lớn mà một máy tính thông thường hoặc máy chủ mạnh không có khả năng thực hiện. Từ khi ra đời, mạng ngàng hàng đã trải qua ba thế hệ: 2
Mạng ngang hàng thế hệ thứ nhất chủ yếu được sử dụng vào mục đích chia sẻ tệp tin với quy mô nhỏ như Napster [8]. Trong hệ thống có một số nút đặc biệt (gọi là máy chủ) làm nhiệm vụ lưu trữ vị trí của các tệp tin. Khi cần tìm kiếm tệp tin, nút tìm kiếm liên hệ với máy chủ để xác định nút chứa tệp tin. Tiếp theo, nút tìm kiếm và nút chứa tệp tin sẽ kết nối trực tiếp với nhau để trao đổi dữ liệu. Mạng ngang hàng thế hệ thứ nhất cho phép tìm kiếm thông tin nhanh chóng, tuy nhiên khả năng mở rộng mạng bị hạn chế do máy chủ bị quá tải khi có nhiều nút tham gia mạng gửi yêu cầu tìm kiếm đến máy chủ. Mạng ngang hàng thế hệ thứ hai khắc phục được điểm yếu của thế hệ thứ nhất. Trong mạng ngang hàng thế hệ thứ hai các nút có vai trò như nhau, không có nút nào đóng vai trò là máy chủ. Khi cần tìm kiếm tệp tin, nút tìm kiếm gửi câu truy vấn tới tất cả các nút tham gia mạng theo kiểu phát tràn (flooding) cho đến khi nút chứa tệp tin được tìm thấy. Sau đó nút nguồn và nút chứa tệp tin kết nối trực tiếp với nhau để trao đổi dữ liệu. Kỹ thuật tìm kiếm theo kiểu phát tràn sinh ra nhiều lưu lượng mạng làm cho khả năng mở rộng mạng của thế hệ thứ hai kém hơn thế hệ thứ nhất. Mạng ngang hàng điển hình cho thế hệ thứ hai là Gnutella [10]. Để giải quyết vấn đề mở rộng phạm vi mạng và khác phục các điểm yếu của mạng ngang hàng thế hệ thứ nhất và thứ hai (các mạng ngang hàng không có cấu trúc), mạng ngang hàng thế hệ thứ ba (mạng ngang hàng có cấu trúc) đã ra đời. Mạng ngang hàng thế hệ thứ ba có các cơ chế tốt hơn để đáp ứng số lượng người dùng ngày càng tăng trong mạng P2P [76]. Các mạng ngang hàng có cấu trúc được phát triển dựa trên cấu trúc bảng băm phân tán (DHT) và sử dụng kỹ thuật tìm kiếm theo cơ chế của bảng băm phân tán DHT. Bảng băm phân tán ra đời để cung cấp cơ chế chỉ mục phân tán, khả năng mở rộng, độ tin cậy và khả năng chịu lỗi. Các mạng ngang hàng có cấu trúc tiêu biểu là: Chord [17], CAN [18], Pastry [19], Tapestry [20], v.v. 3
Trong mạng ngang hàng có cấu trúc, các nút tham gia mạng được tổ chức chặt chẽ. Mỗi nút tham gia mạng được gán một định danh. Định danh của một nút là giá trị băm thông tin đặc trưng của nút đó như: địa chỉ IP, địa chỉ cổng TCP/IP. Cơ chế định tuyến và quản lý của DHT tạo ra các liên kết ảo (liên kết logic) giữa các nút trong mạng, các liên kết ảo này hình thành một mạng phủ ảo (Overlay Network). Truyền thông trực tiếp giữa hai nút tham gia mạng được thực hiện dựa trên các liên kết vật lý của mạng lớp phía dưới (ví dụ mạng Internet). Mạng cho phép mạng phủ ảo hoạt động trên đó được gọi là mạng nền tảng (Underlay Network). Trong DHT, dữ liệu lưu trữ dưới dạng cặp khóa/giá trị (key/value). Mỗi mục dữ liệu lưu trữ trong hệ thống có một định danh duy nhất. Định danh dữ liệu là giá trị băm của tên tệp tin hoặc nội dung tệp tin. Hàm băm dùng để sinh ra định danh của nút và định danh của dữ liệu là giống nhau. Định danh dữ liệu còn được gọi là khóa (key). Mỗi nút tham gia mạng chịu trách nhiệm quản lý một số lượng khóa nhất định. Số lượng các khóa do một nút quản lý phụ thuộc vào chất lượng của hàm băm. Do DHT có khả năng tự tổ chức mạng, khả năng tìm kiếm, khả năng chịu lỗi và mở rộng mạng, v.v. cho nên các nghiên cứu về mạng ngang hàng trong những năm gần đây cơ bản tập trung vào mạng ngang hàng có cấu trúc. Ngoài những ưu điểm trên, DHT cũng tồn tại nhiều yếu tố ảnh hưởng đến hiệu năng hoạt động của hệ thống mạng ngang hàng có cấu trúc. Theo cách hiểu thông thường, hiệu năng là một độ đo công việc mà một hệ thống thực hiện được. Đối với hệ thống mạng ngang hàng có cấu trúc, hiệu năng của hệ thống được xác định bởi sự kết hợp của các nhân tố: tính sẵn sàng (availability), thông lượng (throughput) và thời gian đáp ứng (response time), thời gian trễ (delay), độ tin cậy (reliability), tỉ suất lỗi (error rate), v.v. 4
có yếu tố liên quan đến hệ thống mạng vật lý phía dưới, có yếu tố liên quan đến đặc điểm của mạng ngang hàng có cấu trúc. Luận án này chỉ đề cấp đến nhân tố tính sẵn sàng của dữ liệu liên quan đến đặc điểm của mạng P2P. Các yếu tố ảnh hưởng đến nhân tố tính sẵn sàng của dữ liệu có thể kể đến gồm: - Các nút tham gia mạng không đồng nhất về băng thông, khả năng xử lý, năng lực lưu trữ, thời gian kết nối. Với máy tính bảng, máy tính xách tay hoạt động trong môi trường không dây tham gia mạng thường có thời gian kết nối mạng ngắn, khả năng xử lý, dung lượng lưu trữ thấp. Trong khi đó, các máy tính người dùng, các máy chủ tham gia mạng có tốc độ xử lý mạnh, khả năng lưu trữ lớn, thời gian kết nối mạng dài. Sự không đồng nhất này ảnh hưởng đến khả năng xử lý và định tuyến các câu truy vấn, làm ảnh hưởng đến tỷ lệ thành công của các câu truy vấn, do đó làm ảnh hưởng đến tính sẵn sàng của dữ liệu và làm ảnh hưởng đến hiệu năng hoạt động của hệ thống mạng. - Định danh của nút tham gia mạng và định danh của dữ liệu phân bố không đều trong không gian định danh làm cho một số nút trong mạng phải quản lý nhiều khóa dữ liệu hơn, lưu trữ nhiều dữ liệu hơn các nút khác dẫn tới hiện tượng nút quá tải (các nút không có khả năng xử lý dữ liệu, không có khả định tuyến truy vấn) trong mạng. Ngoài ra, một số dữ liệu có tính phổ biển cao, tỷ lệ truy vấn nhiều cũng ảnh hưởng đến khả năng xử lý truy vấn, khả năng định tuyến truy vấn của một nút, ảnh hưởng đến băng thông mạng. Khi một nút bị quá tải sẽ tác động trực tiếp tỷ lệ thành công của các câu truy vấn và ảnh hưởng đến đến tính sẵn sàng của dữ liệu và làm ảnh hưởng đến hiệu năng hoạt động của hệ thống mạng. - Trong mạng ngang hàng có cấu trúc, các nút thường xuyên ra vào mạng mà không có sự thông báo trước cho nút khác. Khi một nút rời hệ thống, một nút khác phải gánh trách nhiệm quản lý dữ liệu của nút rời mạng, 5
đồng thời các tệp dữ liệu gốc được lưu trữ trên nút rời mạng cũng không tồn tại trong mạng. Điều này dẫn tới cấu trúc của mạng thay đổi liên tục trong khoảng thời gian ngắn làm cho mạng có độ ổn định thấp (hay còn gọi là mạng có "Churn rate" cao) và làm ảnh hưởng đến tính sẵn sàng của dữ liệu trong mạng và do đó làm giảm hiệu năng hoạt động của hệ thống. Đã có nhiều nghiên cứu đề xuất các thuật toán nhằm nâng cao tính sẵn sàng của dữ liệu qua đó nâng cao hiệu năng hoạt động của mạng ngang hàng có cấu trúc. Các hướng nghiên cứu đã đề xuất tập trung vào hai hướng chính: (i) Nâng cao tỷ lệ thành công của các câu truy vấn dữ liệu Các nghiên cứu đã đề xuất nâng cao tỷ lệ thành công của các câu truy vấn được thực hiện theo hướng nâng cao khả năng cân bằng tải cho các nút. Nghiên cứu [27], [28], [37], [38] sử dụng khái niệm server ảo (máy chủ ảo) cho việc cân bằng tải. Mỗi nút vật lý quản lý một hoặc nhiều server ảo. Các server ảo hoạt động như các nút tham gia mạng DHT. Mỗi nút vật lý sẽ chọn một số lượng server ảo tỷ lệ với khả năng của nó để đảm bảo cân bằng tải hoặc có thể dịch chuyển các server ảo giữa các nút để đảm bảo cân bằng tải cho các nút. Tuy nhiên, thuật toán sử dụng server ảo cũng tồn tại một số nhược điểm, như để quản lý được các server ảo thì mỗi nút phải duy trì khá nhiều liên kết đến các server ảo đó. Các nghiên cứu [39], [40], [41], [34] thực hiện việc dịch chuyển định danh của các nút khi trong hệ thống có các nút quá tải để bảo đảm cân bằng tải cho các nút. Nhược điểm của các thuật toán này là làm tăng tải của hệ thống khi dịch chuyển dữ liệu cũng như phải cập nhật lại các liên kết khi định danh của một nút thay đổi. Các nghiên cứu [47], [48], [49], [50], [52] thực hiện việc điều khiển tắc nghẽn để nâng cao khả năng định tuyến của một nút. Nghiên cứu này sử dụng 6
bảng định tuyến cố định và kiểm soát tắc nghẽn bằng cách giảm tốc độ gửi gói tin hoặc sử dụng đường đi khác trong bảng định tuyến và không tính đến khả năng xử lý của các nút trong mạng. Do đó, có thể làm giảm tốc độ truyền của mạng khi xảy ra tắc nghẽn. (ii) Nâng cao tính sẵn sàng của dữ liệu Các nghiên cứu [21], [53], [54], [55] thực hiện sao lưu dữ liệu một nút quản lý đến một số nút láng giềng gần nhất. Cách tiếp cận [18], [56], [57] đặt các bản sao của các tệp dữ liệu ở một số nút khác nhau và định hướng lại các yêu cầu truy vấn đến các nút này. Hướng nghiên cứu [54], [57], [59] thực hiện việc sao lưu nhiều khóa, một khoá có liên hệ với một tập gồm r định danh được lựa chọn trong không gian khóa DHT tương ứng với r nút sao lưu cho một tệp tin. Nghiên cứu [60] tổ chức các nút trong mạng thành các cụm và tạo ra bản sao giữa các nút gần nhau về mặt vật lý (các nút có khoảng cách địa lý gần nhau) dựa trên khả năng lưu trữ sẵn có của các nút, v.v. Các nghiên cứu nâng cao tính sẵn sàng của dữ liệu đã đề xuất cơ bản cải thiện được hiệu năng của hệ thống, tuy nhiên vẫn còn tồn tại nhiều hạn chế như: chi phí di chuyển dữ liệu cao, không bảo đảm vấn đề cân bằng tải giữa các nút, thời gian thực hiện chậm, v.v. Từ những phân tích và đánh giá các nghiên cứu nâng cao tính sẵn sàng của dữ liệu qua đó nâng cao hiệu năng hoạt động của mạng ngang hàng có cấu trúc đã đề xuất trước đây cho thấy còn có nhiều vấn đề giải quyết như: chi phí duy trì dữ liệu lớn, không bảo đảm cân bằng tải giữa các nút nhất là về tải lưu trữ, không tận dụng được khả năng xử lý của các nút, v.v. Do đó, luận án nghiên cứu nâng cao hiệu năng hoạt động của mạng ngang hàng có cấu trúc tập trung vào giải quyết các vấn đề còn tồn tại ở trên. 7
2. Mục tiêu của luận án Luận án phân tích các đặc điểm của mạng ngang hàng có cấu trúc ảnh hướng đến cân bằng tải xử lý truy vấn, khả năng định tuyến của các nút và tính sẵn sàng của dữ liệu trong mạng. Trên có sở đó, luận án đề xuất một số thuật toán nâng cao hiệu năng hoạt động của mạng ngang hàng có cấu trúc. Mục tiêu của các thuật toán đề ra trong luận án là tăng tỷ lệ thành công của các câu truy vấn và nâng cao tính sẵn sàng của dữ liệu qua đó nâng cao hiệu năng hoạt động của mạng. Luận án đề xuất thuật toán cân bằng tải xử lý truy vấn và thuật toán điều khiển tắc nghẽn giúp nâng cao tỷ lệ thành công của các câu truy vấn; đề xuất thuật toán sao lưu dữ liệu để đảm bảo tính sẵn sàng của dữ liệu trong các ứng dụng mạng P2P. 3. Phạm vi nghiên cứu, đối tượng nghiên cứu Để đạt được mục tiêu đề ra, luận án tập trung giải quyết các vấn đề sau: - Phân tích, đánh giá các nghiên cứu đã đề xuất về nâng cao hiệu năng hoạt động của mạng ngang hàng có cấu trúc để làm rõ cách thức tiếp cận, giải quyết vấn đề từ khía cạnh phương pháp luận và xác định công cụ phân tích, mô phỏng sử dụng trong luận án. - Phân tích, đánh giá các nghiên cứu về cân bằng tải trong mạng ngang hàng có cấu trúc từ đó đề xuất thuật toán cân bằng tải để nâng cao hiệu năng hoạt động của hệ thống mạng. - Phân tích, đánh giá các nghiên cứu về điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc và đề xuất thuật toán điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc. - Phân tích, đánh giá các nghiên cứu về sao lưu dữ liệu trong mạng ngang hàng có cấu trúc và đề xuất thuật toán sao lưu dữ liệu trong mạng ngang hàng có cấu trúc. 8