Đồ Án Giải pháp cân bằng tải sử dụng cấu trúc thư mục cho mạng ngang hàng có cấu trúc

MỤC LỤC . . 1
DANH MỤC THUẬT NGỮ . . 3
DANH MỤC HÌNH VẼ 4
MỞ ĐẦU . . 6




CHƯƠNG 1 - TỔNG QUAN VỀ MẠNG NGANG HÀNG .9




1.1 Tổng quan về mạng ngang hàng 9
1.1.1 Khái niệm về mạng ngang hàng 9
1.1.2 Ưu điểm của mạng ngang hàng .10
1.1.3 Nhược điểm của mạng ngang hàng 11


1.2 Phân loại mạng ngang hàng 11
1.2.1 Phân loại theo mức độ tập trung của các node mạng .11
1.2.2 Phân loại theo cấu trúc liên kết 13


1.3 Mạng ngang hàng có cấu trúc dựa trên DHT(Distributed Hash Table)
. .15
1.3.1 Giới thiệu DHT . 15
1.3.2 Mạng chord . 17
a. Mô hình mạng Chord 17
b. Ánh xạ khóa vào một node trong Chord 19
c. Tìm kiếm trong mạng Chord 19
d. Tham gia và ổn định mạng 20


1.4 Kết luận 20






CHƯƠNG 2 - CÂN BẰNG TẢI TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC . 22


2.1 Khái niệm về tải trên mạng ngang hàng 22
2.1.1 Khái niệm .22
2.1.2 Node quá tải 23
2.1.3 Node có tải cao và Node có tải thấp 23


2.2 Các nguyên nhân dẫn đến mất cân bằng tải trên các hệ thống DHT 23
2.2.1 Định danh các node không cân bằng . 23
2.2.2 Định danh dữ liệu không cân bằng 24
2.2.3 Hot spots .25
2.2.4 Khả năng các node không cân bằng . 26
2.2.5 Nhận xét 26



2.3 Các giải pháp cân bằng tải 26
2.3.1 Hướng sử dụng server ảo 27
a. Sử dụng Log(N) Virtual Servers .27
b. Phương pháp Proportion . 28
c. Phương pháp di chuyển Virtual Server (Transfer) . 29
2.3.2 Hướng không sử dụng server ảo 33
Thuật toán cân bằng tải theo ngưỡng 33
2.3.3 Kết luận 39




CHƯƠNG 3 - ĐỀ XUẤT CẢI TIẾN THUẬT TOÁN CÂN BẰNG TẢI THEO
NGƯỠNG . 40




3.1 Một số khái niệm . 41


3.2 Thuật toán ThresholdPlus 41


3.3 Đánh giá: 46




CHƯƠNG 4 - ĐÁNH GIÁ HIỆU QUẢ CỦA GIẢI PHÁP ĐỀ XUẤT DỰA TRÊN MÔ PHỎNG . 48


4.1 Ảnh hưởng thời gian sống của một node tới các thuật toán cân bằng tải .48


4.2 Ảnh hưởng của số lượng các câu truy vấn tới các thuật toán cân bằng tải 49


4.3 Ảnh hưởng của câu truy vấn dạng Zipf tới các thuật toán cân bằng tải 50


4.4 So sánh kết quả thực nghiệm của thuật toán Threshol Plus với các thuật
toán đã có: 51


4.5 Kết luận 52




CHƯƠNG 5 - KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .54




5.1 Kết luận 54


5.2 Hướng phát triển tiếp theo 54















THUẬT NGỮ






Thuật ngữ Ý nghĩa
Based -DHT
Broadcast Chord




Client/Server
DHT (Distributed Hash Table ) Directory




Entry




Finger Table Host Ports Identify
Key
LBM (Load Balancing Matrix) Load
Load-balancing
Node












Overload
P2P (Peer to Peer network) Partial query Predecessor(n)




Query Successor(n)




Target Unilization Workload Dựa trên bảng băm phân tán
Một thông điệp truyền tới tất cả các trạm Một giao thức dựa trên mang ngang hàng có cấu trúc
Máy khách/ Máy chủ
Bảng băm phân tán
Node Thư mục ; Đóng vai trò lưu trữ các thông tin tải của các node
Một bản ghi trong bảng dùng để lưu thông tin về các đặc tả tài nguyên tại mỗi node Bảng định tuyến
Node được truy cập với tần số cao
Định danh Khóa
Ma trận cân bằng tải Tải
Cân bằng tải
Thực thể có khả năng thực hiện một công việc hữu ích nào đó và trao đổi kết quả với các thực thể khác qua mạng một cách trực tiếp hoặc gián tiếp




Quá tải
Mạng ngang hàng Truy vấn từng phần
Node đứng liền sau n (Tính theo chiều kim
đồng hồ)
Truy vấn
Node đứng liền trước n (Tính theo chiều
kim đồng hồ)
Tải lớn nhất mà một node có thể nhận Hệ số sử dụng
Tải làm việc















DANH MỤC HÌNH VẼ






Hình 1. Mô hình mạng ngang hàng 9
Hình 2. Mô hình mạng ngang hàng thuần tuý 12
Hình 3. Hệ thống mạng ngang hàng lai ghép . 13
Hình 4. Tìm kiếm dữ liệu chia sẻ trong Gnutella . 14
Hình 5. Một mạng Chord với 3 node 0, 1, 3 và các bảng Finger Table ứng với mỗi
node. N = 3 bit nên có 3 entry 18
Hình 6. Lưu giữ key trong mạng Chord: node 0 lưu key 6, node 1 lưu key 1 và node 3 lưu key 2 19
Hình 7. Định danh các node không cân bằng 24
Hình 8. Dữ liệu các node không cân bằng .24
Hình 9. Kết quả mô phỏng về sự phân bố dữ liệu không đều nhau 25
Hình 10. Node Host spots . 25
Hình 11.Khả năng các nút không cân bằng . 26
Hình 12.Cân bằng tải sử dụng Log(N) Virtual Servers 28
Hình 13. Tạo mới VS (a) và loại bỏ VS (b) . 29
Hình 14. Node nặng tải di chuyển VS sang node nhẹ tải (nếu chỉ có 1 VS mà vẫn
nặng tải thì sẽ chia làm 2 VS để di chuyển) 30
Hình 15. Phương pháp One - to - One .31
Hình 16. Phương pháp One - to - Many 32
Hình 17. (a) Node A chuyển tải cho node láng riềng B và (b) Chuyển định danh của
node C vào giữa A và B. Độ cao của mỗi hình tương ứng là biểu diễn tải của các node.
34
Hình 18. Node A có tải vượt quá ngưỡng. Node B có tải thấp hơn trong hai láng
riềng của A. Tải được chuyển từ Node A cho Node B 35
Hình 19. Node A có tải vượt quá ngưỡng. Node B có tải thấp hơn trong 2 láng riềng
của A. Tải được chuyển cho node B .35
Hình 20. Node A có tải vượt quá ngưỡng, node E chuyển tải cho F, E di chuyển vị trí đến giữa A và B để nhận tải . 36
Hình 21. Node A có tải vượt quá ngưỡng; Node G là nhẹ tải khi di chuyển không
làm cho Successor(G) bị quá tải; di chuyển vị trí của G đến giữa A và B để G chịu tải
38