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ĩ công nghệ thông tin

ĐẠ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.TS Hồ Sỹ Đàm Hà Nội - 2019 MỤC LỤC MỞ ĐẦU. Mục tiêu của luận án. Phạm vi nghiên cứu, đối tượng nghiên cứu.

Phương pháp nghiên cứu. Đóng góp của luận án. Cấu trúc của luận án. KIẾN THỨC NỀN TẢNG.

Mạng ngang hàng. Ứng dụng mạng ngang hàng. Phân phối nội dung dựa trên mạng ngang hàng. Truyền thông dựa trên mạng ngang hàng.

Xử lý và tính toán phân tán dựa trên mạng ngang hàng. Cộng tác dựa trên mạng ngang hàng. Hạ tầng công nghiệp/nền tảng dựa trên mạng ngang hàng. Các hệ thống cơ sở dữ liệu và tìm kiếm dựa trên mạng ngang hàng.

Các ứng dụng khác. Phân loại mạng ngang hàng. Phân loại theo mức độ phân tán. Phân loại theo cấu trúc mạng ngang hàng.

Mạng ngang hàng có cấu trúc. Mạng ngang hàng Chord. Một số giao thức mạng ngang hàng có cấu trúc khác. CÂN BẰNG TẢI TRONG MẠNG NGANG HÀNG CÓ CẤU TRÚC.

Các nghiên cứu liên quan. Cân bằng tải theo ngưỡng. Cân bằng tải dựa trên server ảo. So sánh các thuật toán cân bằng tải.

Cải tiến thuật toán cân bằng tải theo ngưỡng. Một số khái niệm. Thuật toán ThresholdPlus. Đánh giá thuật toán.

Phương pháp đánh giá. Các kết quả mô phỏng. ĐIỀU KHIỂN TẮC NGHẼN TRONG MẠNG NGANG HÀNG CÓ CẤU TRÚC. Các nghiên cứu liên quan.

Điều khiển tắc nghẽn bằng thay đổi bảng định tuyến. Đánh giá thuật toán. Phương pháp đánh giá. Các kết quả mô phỏng.

SAO LƯU DỮ LIỆU TRONG MẠNG MẠNG NGANG HÀNG CÓ CẤU TRÚC. Các nghiên cứu liên quan. Sao lưu dữ liệu dựa trên phân cụm trong mạng P2P .2 Quản lý thông tin cụm. Sao lưu và truy vấn dữ liệu.

Khôi phục tệp tin. Xây dựng cụm. Đảm bảo tính cục bộ và cân bằng tải. Đánh giá thuật toán.

Phương pháp đánh giá. Các kết quả mô phỏng. Các kết quả đã đạt được. 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. Phân loại mạng ngang hàng.

Phân loại mạng ngang hàng theo mức độ phân tán. Ánh xạ dữ liệu vào mạng DHT. Mạng phủ DHT với 4 nút trong mạng. Vòng Chord với độ dài không gian khóa là 6 bit.

Tìm kiếm đơn giản trên Chord. Bảng finger của nút n8. Giả mã của phương pháp tìm kiếm nâng cao. Quá trình tìm kiếm khóa k54 trên nút n8.

Chuyển tải giữa các nút láng giềng. Khả năng và tải làm việc của một nút. Các nút nhẹ tải thông báo thông tin cho thư mục. 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.

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. Di chuyển định danh để thực hiện cân bằng tải .7 Giả mã của thuật toán ThresholdPlus. 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. 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.

Truy vấn đặt vào các nút ở dạng phân bố Zipf. Chi phí của các thuật toán cân bằng tải. Giả mã thuật toán xử lý tắc nghẽn tại nút n. Giả mã thuật toán xử lý hết tắc nghẽn tại nút n.

Truy vấn thông thường trong mạng Chord (m=6). Tỷ lệ truy vấn thành công khi thay đổi thời gian sống trung bình của nút. Tỷ lệ thành công với số truy vấn đặt vào mỗi nút thay đổi. Tỷ lệ thành công của các truy vấn khi thay đổi ngưỡng mềm 87 Hình 3.

Ảnh hưởng của tham số Zipf đến tỷ lệ thành công của truy vấn. Ả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. Ảnh hưởng của thời gian sống trung bình đến số bước chuyển tiếp truy vấn. Ảnh hưởng truy vấn đặt vào nút đến số thông báo tắc nghẽn.

Ả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. Phạm vi không gian khóa của các cụm. Thông báo cập nhật trong cụm có không gian khóa là [𝐾𝑓𝑑, 𝐾𝑙𝑑]. Ví dụ về sao lưu một tệp dữ liệu.

Giả mã sao lưu dữ liệu tại nút s. Giả mã của thuật toán khôi phục dữ liệu tại nút quản lý khóa. Thủ tục truy vấn và sao lưu tệp tin. Đoạn giả mã thủ tục tách một cụm thành cụm B và C.

Giả mã thủ tục nhập cụm hàng xóm A vào cụm B thành cụm C. Giả mã thủ tục tham gia mạng của một nút. Ví dụ về mô hình Transit stub. 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.

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. 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. 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. Chi phí duy trì với thời gian sống trung bình của các nút khác nhau.

Chi phí duy trì với số nút ra/vào khác nhau. Ả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. Ả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. Ả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. So sánh các thuật toán cân bằng tải. So sánh các thuật toán điều khiển tắc nghẽn. Bảng định tuyến ban đầu của nút ni.

Bảng tìm đường của nút ni sau khi thay đổi. 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. Đặ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.

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).