Luận án Tiến sĩ: Cải thiện hiệu năng định tuyến mạng ngang hàng P2P - Vũ Thị Thúy Hà

i LỜI CAM ĐOAN Tôi cam đoan rằng nội dung của luận án này là kết quả nghiên cứu của bản thân. Tất cả những tham khảo từ các nghiên cứu liên quan đều được nêu rõ nguồn gốc một cách rõ ràng trong danh mục tài liệu tham khảo. Những đóng góp trong luận án là kết quả nghiên cứu đã được công bố trong các bài báo của tác giả và chưa được công bố trong bất kỳ công trình khoa học nào khác. Tác giả luận án Vũ Thị Thúy Hà ii LỜI CẢM ƠN Luận án Tiến sĩ này được thực hiện tại Học viện Công nghệ Bưu chính Viễn thông dưới sự hướng dẫn của PGS.TS Lê Hữu Lập và PGS.TS Lê Nhật Thăng.

Trong suốt quá trình nghiên cứu hoàn thành luận án này, tác giả đã được tập thể các Thầy hướng dẫn định hướng khoa học và tận tình chỉ bảo. Nhân dịp này, tác giả xin kính gửi lòng biết ơn sâu sắc nhất đến các Thầy: PGS.TS Lê Hữu Lập và PGS.TS Lê Nhật Thăng. Các Thầy đã liên tục quan tâm, hướng dẫn và định hướng cho tôi từ cách đặt vấn đề, phương pháp nghiên cứu khoa học, cho đến những công việc cụ thể nhất. Tác giả xin trân trọng cảm ơn Ban Giám đốc Học viện Công nghệ Bưu chính Viễn thông, Hội đồng Khoa học và Đào tạo, Hội đồng Tiến sĩ, Khoa Quốc tế và Đào tạo Sau Đại học của Học viện đã tạo điều kiện thuận lợi cho tác giả được thực hiện và hoàn thành chương trình nghiên cứu của mình.

Xin cảm ơn các Thầy, Cô giáo Khoa Viễn thông 1 và các Thầy, Cô giáo thuộc Học viện Công nghệ Bưu chính Viễn thông về những ý kiến quí báu giúp tác giả hoàn thiện luận án. Chân thành cảm ơn gia đình và bạn bè đã luôn bên cạnh động viên, khích lệ và củng cố tinh thần cho tác giả. Tác giả luận án Vũ Thị Thúy Hà ii MỤC LỤC Lời cam đoan.ii Mục lục.iii Danh mục các ký hiệu các chữ viết tắt.vi Danh mục các bảng.xv Danh mục các hình.xvi MỞ ĐẦU. Tổng quan về mạng P2P.

Tổng quan về mạng ngang hàng. Kiến trúc mạng ngang hàng P2P. Một số các ứng dụng điển hình của mạng ngang hàng. Thách thức khi nghiên cứu mạng ngang hàng P2P.

Tham số hiệu năng mạng ngang hàng. Các hướng tiếp cận nghiên cứu cải thiện hiệu năng mạng ngang hàng. Kết luận chương 1. Phân tích đánh giá hiệu năng thuật toán định tuyến DHTs.

Giới thiệu chung. Bảng băm phân tán - DHT. Một số thuật toán định tuyến DHTs.1 Thuật toán định tuyến Chord.2 Thuật toán định tuyến Tapestry.3 Thuật toán định tuyến Kademlia. Phân tích, đánh giá hiệu năng một số thuật toán định tuyến DHTs.1 Các phương pháp phân tích hiệu năng.2 Lựa chọn công cụ mô phỏng mạng chồng phủ ngang hàng.3 Mô phỏng đánh giá hiệu năng các thuật toán định tuyến DHTs.5 Kết luận chương 2.

Cải thiện hiệu năng thuật toán định tuyến Chord.1 Giới thiệu chung.2 Thuật toán định tuyến Chord.1 Hàm băm nhất quán (Consistent Hasing).2 Định tuyến Chord.3 Tìm kiếm khóa mở rộng Chord.3 Cải thiện hiệu năng thuật toán Chord.1 Phân tích các điểm yếu của thuật toán Chord.2 Phân tích các nghiên cứu cải thiện hiệu năng giải thuật Chord.3 Cải thiện hiệu năng thuật toán Chord.4 Thuật toán Chord cải thiện.5 Mô phỏng đánh giá hiệu năng thuật toán Chord cải thiện.4 Kết luận chương 3. 74 Chương IV. Xây dựng mạng Chord_SL phân cấp cải thiện hiệu năng.1 Giới thiệu chung.2 Mô hình mạng Chord_SL phân cấp.1 Định nghĩa cấu trúc mạng Chord_SL phân cấp.2 Gán định danh SN và ON.3 Lựa chọn SN (supernode) trong mạng Chord_SL.4 Chiến lược tìm kiếm trong mạng Chord_SL.3 Phân tích, đánh giá hiệu năng mạng Chord_SL.1 Độ dài đường tìm kiếm.2 Phân tích dựa trên chi phí.3 Chi phí lựa chọn siêu nút SN.4 Kết luận chương 4. 99 KẾT LUẬN VÀ KIẾN NGHỊ.99 DANH MỤC CÁC CÔNG TRÌNH CÓ LIÊN QUAN ĐẾN LUẬN ÁN.103 TÀI LIỆU THAM KHẢO.

116 vi DANH MỤC CÁC CHỮ VIẾT TẮT Từ viết tắt Tiếng Anh Nghĩa Tiếng Việt A ALM Apllication Layer Multicast Đa hướng lớp ứng dụng AS Autonomous System Hệ thống tự trị API Application Programming Interface Giao diện lập trình ứng dụng AVC Advanced Video Coding Mã hóa video tiên tiến C CAN Content Addressable Networks Mạng địa chỉ nội dung CDF Cumulative Distribution Function Hàm phân bố tích lũy CS Client – Server Mô hình Khách – chủ Csy Centralized Systems Hệ thống tập trung CTMC Continuous Time Markov Chain Chuỗi Markov liên tục theo thời gian Chord_SL An improved chord protocol with Mạng Chord phân cấp hai lớp cải double-layer design and optimal thiện và giải thuật lựa chọn siêu nút supernode selection algorithm tối ưu D DHT Distributed Hash Table Bảng băm phân tán DKS Distributed K-ary System Hệ thống phân tán nhiều chiều DNS Domain Name System Hệ thống tên miền DUSy Decentralized Unstructured Hệ thống phân tán không cấu trúc DSSy Systems Decentralized structured Hệ thống phân tán có cấu trúc Systems DoS Denial of Service Từ chối dịch vụ DTLS Distributed Storage and Lớp bảo mật sao lưu và lưu trữ phân Replication Layer Security tán DTMC Discrete Time Markov Chain Chuỗi Markov thời gian rời rạc F vi FTP File Transfer Protocol Giao thức truyền file G GUI Graphical User Interface Giao diện đồ họa H HTML HyperText Markup Language Ngôn ngữ đánh dấu siêu văn bản HSy Hybrid Systems Hệ thống lai ghép HTTP Hyper-Text Transfer Protocol Giao thức truyền siêu văn bản I ID Identifier Định danh ICMP Internet Control Message Giao thức điều khiển Internet Protocol IETF Internet Engineering Task Force Nhóm chuyên trách kỹ thuật Internet IM Instant Messaging Tin nhắn tức thời IP Internet Protocol Giao thức Internet J JXTA Juxtapose Mạng ngang hàng mã nguồn mở của Sun Microsystems K KBR Key Based Routing Định tuyến dựa trên khóa M MD5 Message-Digest algorithm 5 Thuật toán mã hóa MD5 MDC Multi Description Code Mã hóa đa mô tả N NAT Network Address Translation Chuyển đổi địa chỉ mạng O ONs Ordinary nodes Các nút thông thường OSPF Open Shortest Path First Đường đi ngắn nhất P P2P Peer-to-Peer Ngang hàng PDA Personal Digital Assistant Thiết bị số hỗ trợ cá nhân vi PPP Point-to-Point Protocol Giao thức điểm điểm PRR Prefix routing Định tuyến dựa trên tiền tố Q QoS Quality of Service Chất lượng dịch vụ R RELOAD Resource Location And Discovery Khai phá và tìm kiếm tài nguyên RIP Routing Information Protocol Giao thức thông tin định tuyến RTT Round Trip Time Thời gian gói tin đi tới đích và quay trở về nguồn S SNs Supernodes Các siêu nút SHA1 Secure Hash Algorithm Thuật toán băm bảo mật SHA1 SIP Session Initiation Protocol Giao thức khởi tạo phiên T TCP Transmission Control Protocol Giao thức điều khiển truyền tải TLS Transport Layer Security Bảo mật lớp truyền tải TTL Time To Live Thời gian sống của gói tin U UA User Agent Đại lý người dùng UDP User Datagram Protocol Giao thức lược đồ dữ liệu người dùng URI Uniform Resource Identifier Định danh tài nguyên V VOD Video-on-Demand Video theo yêu cầu VoIP Voice over Internet Protocol Truyền thoại qua giao thức Internet W WAN Wide Area Network Mạng diện rộng ix DANH SÁCH CÁC KÍ HIỆU Tstretch: Tỷ lệ trễ dãn cách trung bình 𝑝(𝑛𝑞,𝑘): Độ dài đường tìm kiếm từ nút có định danh 𝑛𝑞 đến nút có chứa khóa k k: Định danh của khóa tìm kiếm ҡ: Số nút được lưu trữ trong ҡ-buckets của Kademlia 𝑟𝑜𝑜𝑡𝑘: Nút gốc chứa khóa k K: Số nhóm nội miền trong mô hình phân cấp 𝛾: Xác xuất cả nút nguồn và nút đích đều trong cùng một lớp nội miền trong mô hình phân cấp Ҟ: Không gian định danh khóa 𝜌: Tỷ lệ tìm kiếm thành công c(i): Số bước nhảy của mỗi lần tìm kiếm riêng rẽ i 𝑡ℎ: Giới hạn tổng số bước nhảy của mỗi lần tìm kiếm 𝑒𝐼𝐷: Định danh ngoài E: Không gian định danh ngoài I: Không gian định danh nút Ɲ: Số nút trong nhóm nội miền 𝑛𝑞 Định danh của nút q : Định danh của nút n: M: Độ dài bít của định danh nút 𝑇𝑟 : Bảng định tuyến 𝑇𝑟 tại mỗi nút n bao gồm t liên kết đến nút tại một số khoảng cách trong không gian định danh 𝑇𝑠: Bảng định tuyến 𝑇𝑠 tại mỗi nút bao gồm liên kết tới s hàng xóm trực tiếp trong cấu trúc DHT Succ(n): Con trỏ tới nút đầu tiên đứng kề sau nút có định danh n trong không gian định danh theo chiều kim đồng hồ x Pred(n): Con trỏ tới nút đầu tiên đứng kề trước nút có định danh n trong không gian định danh theo chiều kim đồng hồ. N: Kích thước của mạng chồng phủ 𝐹𝑁 (𝑝): Tập các nút hàng xóm của p sn: Định danh của nút nguồn Delay[i]: Trễ giữa nút có định danh n và n.finger[i] nhận được bởi lệnh ping U: Số siêu – siêu nút (Ultra Super-peer) F( S ) : Tập hợp các liên kết của một nút S khi ra nhập vòng Chord của lớp liên miền trong mô hình phân cấp. F( p ) : Tập hợp các liên kết của nút p khi ra nhập vòng Chord của lớp nội miền trong mô hình phân cấp. D: Độ dài định danh của nút trong mô hình Chord_SL phân cấp D: Thiết kế phân cấp D-d: Độ dài bít định danh tiền tố d: Độ dài bít định danh hậu tố fi (xi): Hàm chi phí tương ứng với các biến x1, x2 ,.

𝑡𝑜𝑛(𝑝): Thời gian hoạt động trung bình của nút 𝑃(𝑝): Khả năng xử lý CPU (MIPS Million Instruction Per Second) 𝐵(𝑝): Băng thông của nút h flat : Độ dài đường tìm kiếm qua mô hình Chord_flat h: Độ dài đường tìm kiếm trung bình hns : Độ dài đường tìm kiếm từ nút nội miền đến siêu nút hss : Độ dài đường tìm kiếm siêu nút (SN) trong lớp liên miền Tns : Trễ mạng trung bình giữa một nút trong lớp nội miền và một nút trong lớp liên miền Tss : Trễ mạng trung bình giữa hai nút lớp liên miền Tbeat: Chu kỳ gửi bản tin heartbeat xi Cbeat : Chi phí để gửi bản tin heartbeat Tstab Chu kỳ chạy thuật toán ổn định stabilization Cstab: Chi phí chạy thuật toán ổn định (stabilization) l: Thời gian sống của nút xi DANH MỤC CÁC BẢNG Bảng 2-1. Các tham số dùng cho mô phỏng Kademlia. Các tham số dùng cho mô phỏng Tapestry. Các tham số dùng cho mô phỏng Chord.

Định nghĩa trường trễ Delay[i]. Cấu trúc bảng định tuyến của nút 8. Bảng Finger nghiên cứu [86], [11]. So sánh hiệu năng Chord cải thiện.

Bảng finger Chord_SL. 80 xi DANH MỤC CÁC HÌNH Hình 1-1. Mô hình mạng chồng phủ ngang hàng P2P. Kiến trúc phân lớp điển hình mạng ngang hàng P2P.

Phân loại kiến trúc mạng chồng phủ P2P. Tìm kiếm và lưu trữ dữ liệu trong DHT. Cấu trúc mạng chồng phủ Chord. Quá trình ra nhập, rời mạng.

Bảng định tuyến của nút 5712. Quá trình tìm kiếm từ nút nguồn 5230 tới nút đích 42AD. Quá trình quảng bá chỉ mục dữ liệu. Quá trình truy vấn chỉ mục dữ liệu.

Không gian ID của mạng Kademlia (N=16). Các k-bucket của một nút. Quá trình tìm kiếm.