Đánh giá hiệu năng của một số thuật toán bảng băm phân tán DHT và đưa ra giải pháp cải tiến hiệu năng của thuật toán CHORD

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

---------------------------------------

LUẬN VĂN THẠC SĨ KHOA HỌC

NGÀNH: CÔNG NGHỆ THÔNG TIN

ĐÁNH GIÁ HIỆU NĂNG CỦA MỘT SỐ BẢNG BĂM PHÂN TÁN DHT VÀ ĐƯA RA GIẢI

PHÁP CẢI TIẾN HIỆU NĂNG CỦA THUẬT TOÁN CHORD

NGÔ HOÀNG GIANG

Người hướng dẫn khoa học: TS. NGUYỄN CHẤN HÙNG

HÀ NỘI 2008

BỘ GIÁO DỤC ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

***

Cộng hoà xã hội chủ nghĩa Việt Nam

Độc lập – Tự do – Hạnh phúc

LỜI CAM ĐOAN

Luận văn thạc sỹ này do tôi nghiên cứu và thực hiện dưới sự hướng dẫn của Thầy giáo TS. Nguyễn Chấn Hùng. Để hoàn thành bản luận văn này, ngoài các tài liệu tham khảo đã liệt kê, tôi cam đoan không sao chép các công trình hoặc thiết kế tốt nghiệp của người khác.

Hà Nội, ngày 28 tháng 10 năm 2008 (Ký và ghi rõ họ tên)

Ngô Hoàng Giang

LỜI CẢM ƠN

Trước hết tôi vô cùng biết ơn sâu sắc đến Thầy giáo TS. Nguyễn Chấn Hùng – người đã trực tiếp dành nhiều thời gian tận tình hướng dẫn, cung cấp những thông tin quý báu giúp đỡ tôi hoàn thành bản luận văn này.

Tôi xin chân thành cảm ơn Ban lãnh đạo Trung tâm mạng thông tin – Trường Đại học Bách khoa Hà Nội, nơi tôi đang công tác đã tạo nhiều điều kiện động viên khích lệ để tôi có thể hoàn thành bản luận văn này.

Sau cùng tôi xin bày tỏ lòng biết ơn đến người thân cùng bạn bè đồng nghiệp, những người luôn cổ vũ động viên tôi hoàn thiện bản luận văn này.

Hà Nội, ngày 28 tháng 10 năm 2008

Ngô Hoàng Giang

Mục lục

ULỜI CAM ĐOANU 1

ULỜI CẢM ƠNU 2

UMục lụcU 3

UDanh mục thuật ngữU 5

UDanh mục hình vẽU 6

UDanh mục thuật toánU 8

UDanh mục bảngU 9

ULời mở đầuU 10

UChương 1.U ULý thuyết tổng quanU 11

U1.1.U ULý thuyết chung về về mạng P2PU 11

U1.1.1.U UKhái niệm mạng P2PU 11

U1.1.2.U UQuá trình phát triển của các hệ thống P2PU 12

1U .1.3.U UỨng dụng p2pU 16

U1.1.4.U UCác vấn đề đối với mạng p2p hiện nayU 16

U1.2.U ULý thuyết về Distributed Hash Table (DHT)U 18

U1.2.1.U UHash Table (bảng băm)U 18

U1.2.2.U UDistributed Hash TableU 18

U1.3.U UGiới thiệu một số DHTU 20

U1.3.1.U UChordU 21

U1.3.2.U UKademliaU 30

U1.3.3.U UTapestryU 33

U1.3.4.U UKelipsU 38

U1.4.U UCác phương pháp đánh giá, thử nghiệm mạng P2PU 40

U1.4.1.U UKhảo sát các simulator mô phỏng mạng overlayU 41

U1.4.2.U UP2PSimU 42

UChương 2.U UĐánh giá hiệu năng một số DHTU 43

U2.1.U UBài toán thực tếU 43

U2.2.U UĐánh giá hiệu năng một số DHTU 44

U2.2.1.U UMục tiêu và cơ sở lý luậnU 44

U2.2.2.U UQuá trình thực nghiệm và phương pháp đánh giá hiệu năngU 45

U2.2.3.U UXác định ngưỡng churn rate các DHT làm việc tốtU 47

U2.2.4.U USo sánh hiệu năng của các DHTU 53

U2.2.5.U UĐánh giá ảnh hưởng của các tham số thiết kế đến hiệu năng các DHTU ..63

UChương 3.U UCải tiến hiệu năng của ChordU 68

U3.1.U UHạn chế của giao thức ChordU 68

U3.2.U UGiải pháp cải tiến giao thức ChordU 68

U3.3.U UGiải pháp duy trì vòng dùng cơ chế lockU 69

U3.3.1.U UMục tiêuU 69

3U .3.2.U UCơ chế làm việcU 69

U3.4.U UGiải pháp caching proxyU 79

U3.4.1.U UMục tiêuU 79

U3.4.2.U UCơ chế làm việcU 79

U3.5.U UGiải pháp dùng nhân bản đối xứng cải tiếnU 87

U3.5.1.U UMục tiêuU 87

U3.5.2.U UCơ chế làm việcU 87

UKết luậnU 92

UTài liệu tham khảoU 93

Danh mục thuật ngữ

Tiếng Anh

Tiếng Việt
Peer-to-peer	Mạng ngang hàng
Peer	Đồng đẳng trong mạng ngang hàng
Node	Một thiết bị nối mạng (một peer)
Item	Một đơn vị dữ liệu
Structured	Có cấu trúc
Overlay	Mạng được xây dựng trên các mạng khác
Hash table	Bảng băm
Distributed hash table	Bảng băm phân tán
Join	Gia nhập (mạng ngang hàng)
Leave	Rời khỏi (mạng ngang hàng)
Failure	Lỗi
Churn rate	Số lượng peer rời khỏi/gia nhập mạng trong một khoảng thời gian.