Luận vă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

1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐỖ CAO MINH 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 LUẬN VĂN THẠC SĨ 2 Hà Nội - 2010 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 3 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 4 THUẬT NGỮ Thuật ngữ Ý nghĩa Based -DHT Dựa trên bảng băm phân tán Broadcast Một thông điệp truyền tới tất cả các trạm Chord Một giao thức dựa trên mang ngang hàng có cấu trúc Client/Server Máy khách/ Máy chủ DHT (Distributed Hash Table ) Bảng băm phân tán Directory Node Thư mục ; Đóng vai trò lưu trữ các thông tin tải của các node Entry 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 Finger Table Bảng định tuyến Host Ports Node được truy cập với tần số cao Identify Định danh Key Khóa LBM (Load Balancing Matrix) Ma trận cân bằng tải Load Tải Load-balancing Cân bằng tải Node 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 Overload Quá tải P2P (Peer to Peer network) Mạng ngang hàng Partial query Truy vấn từng phần Predecessor(n) Node đứng liền sau n (Tính theo chiều kim đồng hồ) Query Truy vấn Successor(n) Node đứng liền trước n (Tính theo chiều kim đồng hồ) Target Tải lớn nhất mà một node có thể nhận Unilization Hệ số sử dụng Workload Tải làm việc 5 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 6 Hình 22. Các node nhẹ tải A và F hỏi successor của nó (các đường mũi tên nét liên) và thông báo tình trạng tải cho thư mục 1 và thư mục 2 (các đường mũi tên nét đứt).43 Hình 23. Node A thực hiện cân bằng tải, node láng riềng B nhận tải hộ node A bằng cách dịch chuyển định danh về phía A .......................................................................44 Hình 24. Node A thực hiện cân bằng tải, node A chia tải cho node láng giềng B bằng cách dịch chuyển định danh của A về phía B. ............................................................44 Hình 25. Node A hỏi thư mục 1 để tìm một node nhẹ tải có thể dịch chuyển được (đường mũi tên nét liên). Định danh của node nhẹ tải E được chuyển đến giữa predecessor(A) và A để nhận tải hộ node A (đường mũi tên nét đứt). ........................45 Hình 26. Thời gian sống trung bình của một node thay đổi, các câu truy vấn thực hiện với phân bố Zipf và Uniform. ....................................................................................49 Hình 27. Số câu truy vấn đặt vào một node thay đổi, truy vấn được phân bố ở dạng Zipf và Uniform.........................................................................................................50 Hình 28. Truy vấn đặt vào các node ở dạng phân bố Zipf với tỷ lệ thay đổi. ............51 Hình 29. So sánh ThresholdPlus với Tranfer và Propotion. ......................................52 7 MỞ ĐẦU Một kiểu kiến trúc mạng mới với tên là mạng ngang hàng (Peer to Peer - P2P) đã phát triển nhanh chóng trên internet. Trong đó hoạt động của mạng chủ yếu dựa vào khả năng tính toán và băng thông của các máy tham gia chứ không tập trung vào một số nhỏ các máy chủ trung tâm như các mạng thông thường. Sự phát triển nhanh chóng của mạng ngang hàng trong những năm gần đây thúc đẩy sự ra đời của nhiều ứng dụng mạng như các hệ thống chia sẻ file, tìm kiếm thông tin, tính toán lưới… Mạng ngang hàng có cấu trúc ra đời đảm bảo cho tính hiệu quả cũng như khả năng mở rộng của các ứng dụng này. Tuy nhiên, để đảm bảo chất lượng dịch vụ cho các ứng dụng xây dựng trên mạng ngang hàng có cấu trúc cần phải giải quyết vấn đề cân bằng tải trong mạng ngang hàng có cấu trúc. Có hai hướng tiếp cận chính cho các thuật toán cân bằng tải đó là: hướng tiếp cận dựa trên server ảo (virtual server) và hướng tiếp cận không dựa trên server ảo. Trong luận văn này tôi tập trung vào hướng tiếp cận không dựa trên server ảo và đưa ra một giải thuật cải tiến của giải thuật cân bằng tải theo ngưỡng. Giải thuật của chúng tôi đưa ra cho phép các node quá tải tìm chính xác và nhanh chóng một node phù hợp để thực hiện việc cân bằng tải. Chúng tôi đã cài đặt và thử nghiệm thuật toán đề xuất trong điều kiện mạng gần với thực tế và thấy rằng thuật toán của chúng tôi giải quyết tốt vấn đề cân bằng tải của các node trong mạng. Nội dung luận văn gồm 5 chương cụ thể cho từng chương như sau: Chương 1: Giới thiệu tổng quan về mạng ngang hàng, những khái niệm cơ bản về mạng ngang hàng đồng thời giới thiệu giao thức Chord, giao thức được sử dụng để triển khai mạng phủ DHT khi xây dựng chương trình mô phỏng. Chương 2: Tìm hiểu về vấn đề cân bằng tải trên mạng ngang hàng, một số nguyên nhân dẫn đến mất cân bằng tải, các giải pháp đã được đề xuất và phân tích về các giải pháp này. 8 Chương 3: Trên cơ sở các vấn đề tìm hiểu được ở chương 2. Chúng tôi đề xuất giải pháp cân bằng trên mạng ngang hàng có cấu trúc theo hướng không sử dụng server ảo. Đó là một giải thuật cải tiến của giải thuật cân bằng tải theo ngưỡng. Chương 4: Trình bày cách thực hiện chương trình mô phỏng đồng thời trình bày kết quả đánh giá giải thuật cân bằng tải dựa trên mô phỏng của chúng tôi. Chương 5: Trình bày các công việc mà chúng tôi đã thực hiện được, những vấn đề còn tồn tại của luận văn và hướng phát triển tiếp theo của chúng tôi. 9 CHƯƠNG 1 - TỔNG QUAN VỀ MẠNG NGANG HÀNG Trong chương này, luận văn sẽ giới thiệu khái quát về mạng ngang hàng, các đặc điểm, các hình thức phân loại của mạng ngang hàng, khái niệm về DHT và mạng hàng có cấu trúc đồng thời giới thiệu về một số mạng ngang hàng đã và đang được ứng dụng có hiệu quả. 1.1 Tổng quan về mạng ngang hàng 1.1.1 Khái niệm về mạng ngang hàng Mạng ngang hàng là một mạng mà kiến trúc của nó được tạo nên bởi các máy tính liên kết với nhau, các máy tính tham gia trong mạng đều bình đẳng như nhau và được gọi là các peer, mỗi máy tính tham gia mạng là một phần và duy trì sự tồn tại của mạng. Các máy tính trong mạng thường xuyên liên lạc với các máy tính khác để ổn định mạng và chia sẻ dữ liệu với nhau. Dữ liệu được chứa trên các máy tính và được chia sẻ trực tiếp với nhau giữa các máy tính tham gia vào mạng. Hình 1. Mô hình mạng ngang hàng 10 Ứng dụng thường xuyên gặp nhất của mạng ngang hàng là chia sẻ tệp tin, tất cả các dạng như: âm thanh, hình ảnh, dữ liệu.. hoặc để truyền dữ liệu thời gian thực… . Việc sử dụng mạng ngang hàng mang lại nhiều ưu điểm cho người dùng . Luận văn xin trình bày một số ưu điểm của mạng ngang hàng. 1.1.2 Ưu điểm của mạng ngang hàng Mục đích quan trọng của mạng ngang hàng là các máy tính tham gia mạng đều đóng góp tài nguyên bao gồm băng thông, lưu trữ, khả năng tính toán. Do đó khi càng nhiều mày tính tham gia mạng thì khả năng tổng thể của mạng càng lớn. Do việc các thông tin lưu trữ không chỉ trên máy chủ mà còn được lưu trữ ở chính các máy tham gia mạng nên mô hình này rất phù hợp với tính phi tập trung của Internet. Xét về khía cạnh sức mạnh xử lý, mạng ngang hàng có khả năng xử lý cao hơn cả những máy chủ lớn hiện nay, do đó sử dụng mạng ngang hàng có thể cải thiện đáng kể hiệu quả của các phương pháp phân tích, xử lý dữ liệu và giải các bài toán phức tạp. Sở dĩ làm được như vậy là vì mạng ngang hàng có thể tận dụng được khả năng xử lý, khả năng lưu trữ còn thừa của các máy tham gia mạng với những thuật toán phân tán hợp lý. Công nghệ này đã chia việc xử lý lớn ra thành nhiều việc xử lý để có thể giao cho các máy tính khác trong mạng cùng thực hiện. Mỗi máy tính sẽ xử lý một phần công việc và trả về kết quả xử lý cho máy tính trung tâm, máy tính trung tâm sẽ ghép nối các kết quả này lại với nhau. Bằng cách như vậy, ta có thể giải quyết các bài toán phức tạp yêu cầu vấn đề xử lý, lưu trữ lớn mà không cần phải nâng cấp khả năng xử lý của hệ thống hiện tại. Tính chất phân tán của mạng ngang hàng cũng giúp cho việc phân tán trách nhiệm cung cấp dịch vụ đến tất cả các node trên mạng, nó sẽ loại bỏ được vấn đề ngừng trệ dịch vụ do nơi cung cấp duy nhất gặp sự cố. Đối với mô hình tập trung, chỉ cần máy chủ gặp sự cố thì cả hệ thống sẽ ngưng trệ. Còn đối với mạng ngang hàng, máy tính có thể tham gia hoặc rời khỏi mạng bất kỳ lúc nào mà mạng vẫn hoạt động bình thường, các máy tính còn lại vẫn có thể trao đổi thông tin và chia sẻ tài nguyên cho nhau. Bên cạnh nhiều ưu điểm đã được nêu ở trên thì mạng ngang hàng cũng còn tồn tại một số nhược điểm 11 1.1.3 Nhược điểm của mạng ngang hàng Do các máy tính trên mạng ngang hàng đều có vai trò như nhau và không tuân theo bất cứ một quy luật định tuyến hay kết nối nào, việc yêu cầu dịch vụ được đáp ứng tuỳ biến nên máy yêu cầu dịch vụ có thể nhận được nhiều kết quả khác nhau, khi nó kết nối đến nhiều máy tính khác nhau cùng cung cấp một dịch vụ. Các yêu cầu gửi đi có thể không nhận được kết quả trả về vì không có gì đảm bảo sẽ tồn tại một máy nào đó có khả năng đáp ứng yêu cầu đó. Do đặc điểm là các node có thể rời mạng bất kì lúc nào nên có thể bị ngắt kết nối tới các node này bất cứ thời điểm nào. 1.2 Phân loại mạng ngang hàng Mạng ngang hàng có nhiều tiêu trí phân loại khác nhau, trong luận văn này xin được trình bày hai tiêu trí phân loại mạng ngang hàng đó là: Phân loại theo mức độ tập trung của các node mạng và phân loại theo cấu trúc liên kết của các node. 1.2.1 Phân loại theo mức độ tập trung của các node mạng Nếu lấy tiêu chí về mức độ tập trung của các node mạng, mạng ngang hàng có thể phân làm 2 loại: mạng ngang hàng thuần tuý và mạng ngang hàng lai a. Mạng ngang hàng thuần tuý Trong mạng ngang hàng thuần tuý thì vai trò của các máy trong mạng là ngang nhau và trong mô hình mạng này đã loại bỏ sự tồn tại của các máy chủ tập trung. Trong mạng này đã khắc phục được vấn đề node nghẽn cổ chai trong mô hình tập trung. Tuy nhiên vấn đề tìm kiếm trong mạng ngang hàng thuần tuý sử dụng cơ chế phát tràn (Flooding), yêu cầu tìm kiếm được gửi tới tất cả các node mạng là láng giềng với nó, điều này làm tăng đáng kể lưu lượng trong mạng. 12 Hình 2. Mô hình mạng ngang hàng thuần tuý b. Mạng ngang hàng lai ghép Trong mô hình này, các peer lưu giữ nội dung chia sẻ với các node khác ở trên mạng. Tất cả các peer đều kết nối tới một server, server này lưu giữ thông tin về: - Bảng thông tin kết nối của người dùng đăng kí (địa chỉ IP, băng thông kết nối…) - Bảng liệt kê danh sách các file mà các peer nắm giữ và chia sẻ ở trên mạng cùng với các thông tin mô tả về các files ( tên file, ngày tạo…) Tất cả các peer muốn kết nối vào mạng đều phải liên lạc với server và thông báo với server các file mà nó có. Một peer mà muốn tìm kiềm một file, yêu cầu tìm kiếm được chuyển cho server, server tìm kiếm trong thông tin chỉ mục của mình và trả lại danh sách các peer có thông tin cần tìm. Peer tìm kiếm sẽ liên lạc trực tiếp với các peer có thông tin theo yêu cầu tìm kiếm để tải thông tin trực tiếp từ các peer này. 13 Hình 3. Hệ thống mạng ngang hàng lai ghép 1.2.2 Phân loại theo cấu trúc liên kết Mạng phủ bao gồm tất cả các node mạng đại diện cho các máy tham gia và các liên kết giữa các node mạng này. Một liên kết tồn tại giữa hai node mạng khi một node mạng biết vị trí của node mạng kia. Dựa vào cấu trúc liên kết trong mạng phủ người ta có thể phân loại mạng ngang hàng thành hai loại: mạng ngang hàng không có cấu trúc và mạng ngang hàng có cấu trúc. a. Mạng ngang hàng không có cấu trúc Một mạng ngang hàng được gọi là mạng ngang hàng không có cấu trúc khi liên kết giữa các node trong mạng phủ được thiết lập ngẫu nhiên (tức là không theo một quy luật nào cả). Những mạng như vậy dễ dàng xây dựng vì khi một node muốn tham gia mạng có thể lấy liên kết có sẵn của một node khác đang ở trong mạng và sau đó dần dần tự bản thân nó sẽ thêm vào các liên kết mới của riêng mình. Trong mạng ngang hàng không có cấu trúc, khi một node muốn tìm kiếm một dữ liệu, thì yêu cầu tìm kiếm sẽ truyền trên toàn bộ mạng để tìm ra càng nhiều máy tính chia sẻ càng tốt. Hệ thống này thể hiện rõ nhược điểm là không có gì đảm bảo là việc tìm kiến thành công. Đối với dữ liệu phổ biến được chia sẻ trên nhiều máy thì tỉ lệ thành công là khá cao, ngược lại nếu dữ liệu chỉ được 14 chia sẻ trong một vài máy thì xác suất tìm thấy là rất nhỏ. Tính chất này là hiển nhiên trong mạng ngang hàng không có cấu trúc vì không có bất kỳ mối tương quan nào giữa một máy và dữ liệu của nó quản lý trong mạng, do vậy yêu cầu tìm kiếm được chuyển một cách ngẫu nhiên đến một số máy trong mạng. Số máy trong mạng càng lớn thì khả năng tìm thấy thông tin càng nhỏ. Do khi muốn tìm kiếm trên mạng ngang hàng không có cấu trúc, yêu cầu tìm kiếm được phát trên toàn mạng nên không có cấu trúc định hướng, một yêu cầu thường chuyển cho số lượng lớn các máy tính trong mạng làm tiêu tốn băng thông, dẫn đến hiệu quả tìm kiếm thấp. Một mô hình mạng ngang hàng không cấu trúc điển hình đó là mạng Gnutella. Các máy tính trong Gnutella được mô tả như là những “servent”, các thành viên trong mạng và được chia sẻ file. Các máy tính khác có thể lấy được những file chia sẻ này. Việc tìm kiếm file trên mạng mô tả trong hình 4, khi một máy tính A tìm kiếm file X, nó sẽ gửi một truy vấn broadcast tới tất cả các máy tính nó biết, được coi là hàng xóm của nó. Truy vấn sau đó sẽ được chuyển dần qua các bước và tới được máy tính có chứa file X. Gnutella có mã nguồn mở và có giao thức mô tả rõ ràng trên mạng Internet, bất cứ ai quan tâm cũng có thế tìm hiểu và phát triển để tạo ra một mạng ngang hàng của riêng mình với các tính năng muốn có. Hình 4. Tìm kiếm dữ liệu chia sẻ trong Gnutella 15 b. Mạng ngang hàng có cấu trúc Mạng ngang hàng có cấu trúc khắc phục nhược điểm của mạng không cấu trúc bằng cách sử dụng hệ thống Bảng Băm Phân Tán (DHT: Distributed Hash Table). Hệ thống này định nghĩa liên kết giữa các nút mạng trong mạng phủ theo một thuật toán cụ thể, đồng thời xác định chặt chẽ mỗi nút mạng sẽ chịu trách nhiệm đối với một phần dữ liệu chia sẻ trong mạng. Với cấu trúc này, khi một máy cần tìm một dữ liệu, nó chỉ cần áp dụng một giao thức chung để xác định nút mạng nào chịu trách nhiệm cho dữ liệu đó và sau đó liên lạc trực tiếp đến nút mạng đó để lấy kết quả.Việc tìm kiếm thông tin trên mạng ngang hàng có cấu trúc cũng nhanh hơn so với mạng ngang hàng không có cấu trúc. Nếu như mạng ngang hàng không có cấu trúc các máy tính gửi thông điểm broadcast để tìm kiếm thông tin thì trong mạng ngang hàng có cấu trúc một máy tính chỉ cần gửi thông điệp tìm kiếm qua một số máy tính. Giao thức tìm kiếm chung trong mạng sẽ đảm bảo thông tin sẽ được tìm thấy. Một số mạng ngang hàng có cấu trúc nổi tiếng như: Chord, CAN, Kademlia, pastry… trong đó Chord và CAN được mô tả chi tiết, đã được mô phỏng và cho kết quả qua các bài báo. Trong phần tiếp theo luận văn xin trình bày chi tiết về giao thức mạng Chord. 1.3 Mạng ngang hàng có cấu trúc dựa trên DHT(Distributed Hash Table) 1.3.1 Giới thiệu DHT Các nghiên cứu về DHT được bắt nguồn cùng với sự phát triển của các hệ thống P2P như Napster, Gnutella, và Freenet, những hệ thống này sử dụng lợi thế của các tài nguyên phân tán trên mạng Internet để cung cấp một ứng dụng đơn hữu dụng. Cụ thể, chúng đã sử dụng lợi thế tăng băng thông và sức chứa của ổ cứng còn nhàn rỗi của các Peer để cung cấp dịch vụ chia sẻ file. Những hệ thống này khác nhau ở cách thức thực hiện việc tìm kiếm dữ liệu mà các peer quản lý. Napster sử dụng một server trung tâm: mỗi node khi tham gia vào mạng sẽ gửi một danh sách các file được lưu trữ ở máy lên cho server, server sẽ xử lý các truy vấn, tìm các file trong danh sách, rồi gửi đường dẫn tới node chứa các file cần tìm. Thành phần trung tâm này tạo ra một điểm yếu trong hệ thống vì có thể bị tấn công hoặc có thể bị kiện cáo về bản quyền. Gnutella và những mạng tương tự chuyển sang sử dụng mô hình phát tràn các thông điệp truy vấn (flooding query model), mỗi truy vấn được đưa ra tương ứng với việc một thông điệp được broadcast tới tất cả các node có trong mạng. Vì vậy, mặc 16 dù tránh được điểm yếu của thành phần trung tâm như trên, thì phương pháp này lại kém hiệu quả hơn so với Napster. Cuối cùng, Freenet thực sự là phân tán, nó sử dụng cơ chế routing dựa trên khóa, mỗi file được gán một khóa, các khóa gần giống nhau sẽ cùng được lưu ở một tập các node. Các truy vấn sẽ được định tuyến đi trong mạng mà không phải ghé thăm tất cả các node có trên mạng. Tuy nhiên, Freenet không đảm bảo dữ liệu sẽ được tìm thấy. DHT sử dụng cơ chế định tuyến dựa trên khóa trên một kiến trúc mạng chặt chẽ hơn để có thể đạt được cả tính phân tán về tài nguyên của Gnutella và Freenet, tính hiệu quả về truy vấn của Napster. Có một hạn chế là DHT chỉ hỗ trợ tìm kiếm chính xác chứ không hỗ trợ tìm kiếm theo từ khóa, hay tìm kiếm theo khoảng, tuy nhiên các chức năng này có thể triển khai mở rộng trên nền DHT. Distributed hash tables (DHTs) là hệ thống mạng phân tán, cung cấp các dịch vụ tìm kiếm dựa vào bảng băm. Bảng băm là một cặp ( tên, giá trị). Mỗi một node khi tham gia vào mạng có thể dễ dàng tìm thấy giá trị mong muốn dựa vào tên của giá trị đó. Việc hình thành tên (khóa) và gắn các khóa đó với giá trị tương ứng được thực hiện trực tiếp tại các node trong mạng, chính vì vậy khả năng sập mạng được giảm tối thiểu khi các node tham gia hoặc dời bỏ mạng. Chính lý do này khiến khả năng mở rộng của mạng DHT là cực lớn, quá trình kiểm soát việc tham gia, dời bỏ mạng của các node cũng trở nên dễ dàng hơn. Với cấu trúc vững mạnh, DHT được sử dụng để xây dựng nhiều ứng dụng phức tạp như: Hệ thống các file phân tán, hệ thống chia sẻ file ngang hàng, hệ thống nội dung phân tán, tin nhắn tức thời, Multicast… Các mạng DHT nổi tiếng thường được nhắc đến là: Bittorrent, eDonkey network, Yacy… Một số mạng based - DHT đầu tiên như CAN, Chord được giới thiệu cùng thời gian năm 2001. Từ đó lĩnh vực nghiên cứu này trở lên khá sôi động. Công nghệ DHT đã được sử dụng như một thành phần của BitTorrent. DHT nhấn mạnh vào các thuộc tính sau:  Không tập trung (Decentralization): Các node tham gia cấu thành hệ thống không có thành phần trung tâm làm điều phối mạng.  Khả năng mở rộng: Hệ thống vẫn có thể hoạt động hiệu quả với hàng nghìn hoặc hàng triệu node. 17  Khả năng chịu lỗi: Hệ thống vẫn có thể làm việc ổn định ngay cả khi có các sự kiện node tham gia, rời bỏ, lỗi diễn ra liên tục. Kỹ thuật khóa được sử dụng để đạt được mục đích là mỗi node chỉ cần liên kết với một số ít các node khác trong hệ thống, thường là O(logn) với n là số node tham gia. Vì vậy sự thay đổi trong các thành viên chỉ ảnh hưởng đến một phần nhỏ của hệ thống. Một số thiết kế DHT tìm đến tính bảo mật chống lại những người tham gia ác tâm và cho phép người tham gia giấu danh tính, mặc dù điều này không phổ biến trong các hệ thống P2P chia sẻ file. Cuối cùng, DHT phải giải quyết những vấn đề cơ bản của các hệ thống phân tán đó là cân bằng tải, tính toàn vẹn dữ liệu, hiệu năng (cụ thể là đảm bảo các hoạt động như định tuyến, lưu trữ, truy vấn phải được thực thi nhanh chóng). 1.3.2 Mạng chord Theo một đánh giá tổng hợp về các thuật toán định tuyến dựa trên DHT trong các kiến trúc mạng khác nhau như hình tròn (ring, với giao thức Chord), hình cây (tree), hình hộp (hypercube, với giao thức CAN), …xét về sự linh hoạt trong việc định tuyến, khả năng phục hồi trạng thái cũng như khả năng chịu lỗi, kiến trúc Ring đều được đánh giá cao. Vì vậy, kiến trúc Chord[1] thường hay được sử dụng như là mạng phủ để thực hiện các cài đặt cải tiến việc các ứng dụng, xử lý trên P2P có cấu trúc. a. Mô hình mạng Chord Chord[1] được mô tả dưới dạng một vòng tròn và không gian định danh phân bố đều trên vòng tròn tăng dần theo chiều kim đồng hồ. Nếu gọi N là số bit định danh của không gian thì mạng Chord có thể chứa tối đa 2N node. Mỗi node trên Chord có một định danh id và duy trì liên kết 2 chiều với node đứng liền trước và liền sau nó theo chiều kim đồng hồ tạo thành một mạch liên kết vòng. Node liền trước được gọi là Successor(id), và node liền sau được gọi là Predecessor(id). Thêm vào đó, một node sẽ lưu một bảng định tuyến gọi là Finger Table, cho phép node đó định tuyến tới các node ở xa. Mỗi dòng trong bảng Finger Table sẽ lưu thông tin về 1 node ở xa, gọi là 1 entry. Không gian định danh có bao nhiêu bit thì Finger Table có bấy nhiêu entry. 18 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 Các trường trong mỗi entry trong bảng Finger Table được định nghĩa trong bảng dưới: Notation Definition Finger[k].start (n+2k-1) mod 2m, 1 ≤ k ≤ m .interval (finger[k].start, finger[k+1].start .node First node ≥ n.finger[k].start Successor The next node on ther identifier circle; Finger[1].node Predecessor The previous node on the identifier circle Trong đó giá trị của trường node tại dòng i của bảng được coi như là finger thứ i của node n. Thông tin lưu trong bảng cũng bao gồm cả IP và Port của các node liên quan. Node đầu tiên trong bảng Finger Table của n chính là Successor của n, hay còn được gọi là Immediate Successor. 19 Từ bảng Finger Table ở trên ta có thể thấy rằng: + Mỗi node chỉ cần lưu trữ thông tin của một số node nhất định trong bảng định tuyến của mình. + Node biết thông tin về các node gần nó nhiều hơn là các node ở xa. + Bằng cách sử dụng bảng Finger Table một node n có thể xác định được vị trí của bất kỳ khóa nào trên mạng. b. Ánh xạ khóa vào một node trong Chord Chord[1] ánh xạ các khóa vào các node, thường sẽ là một cặp key và value. Một value có thể là 1 address, 1 văn bản, hoặc 1 mục dữ liệu. Chord có thể thực hiện chức năng này bằng cách lưu các cặp key/value ở các node mà key được ánh xạ. Một node sẽ chịu trách nhiệm lưu giữ một khóa k nếu node đó là node có định danh id nhỏ nhất và id lớn hơn k. Một node khi lưu giữ khóa k cũng sẽ được gọi là Successor của k, ký hiệu là Successor(k). 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. c. Tìm kiếm trong mạng Chord Khi một node n cần tìm kiếm một khóa có định danh id, node n sẽ tìm node chịu trách nhiệm lưu giữ id đó. Nếu node n ở xa so với vị trí của node lưu giữ id, n có thể nhờ vào thông tin trong bảng Finger Table để định tuyến đến các node xa hơn, từ đó dần dần tìm ra node chịu trách nhiệm lưu giữ id. 20 Một ví dụ được chỉ trong hình 8, giả sử node 3 muốn tìm successor của ID = 1 (hoặc còn có thể coi là khóa). ID =1 thuộc khoảng [7, 3). Node 3 kiểm tra entry thứ 3 trong bảng định tuyến của nó, là 0. Bởi vì 0 nằm ngay trước 1 trên vòng tròn, node 3 sẽ hỏi node 0 để tìm successor của 1. Tiếp theo, node 0 sẽ tìm trong bảng định tuyến của nó và suy ra successor của 1 chính là node 1, và trả lời node 3 rằng node 1 chính là successor của khóa ID = 1. d. Tham gia và ổn định mạng Trong 1 mạng động, thường xuyên có sự thay đổi với các node tham gia và rời khỏi bất kì lúc nào. Để có thể xác định được vị trí của các khóa ở trong mạng, Chord cần thỏa mãn 2 điểm sau:  Mỗi successor của một node phải được duy trì đúng  Với mỗi khóa k, node successor(k) có trách nhiệm quản lý k Khi tham gia vào một mạng Chord, một node n cần chọn cho nó một định danh id và báo cho các node bên cạnh biết sự tham gia của nó. Các node Successor và Predecessor sẽ cần phải cập nhật thông tin về node mới tham gia vào mạng. Node n cũng khởi tạo bảng định tuyến Finger Table. Để mạng vẫn định tuyến đúng sau khi có sự tham gia của node n, các node cần thường xuyên chạy thuật toán ổn định mạng để cập nhật thông tin về node bên cạnh (hay node láng giềng). Một số node có lưu thông tin về n trong bảng Finger Table thì cần cập nhật các entry liên quan trong Finger Table. Cuối cùng, node Successor của n sẽ chuyển một phần khóa k mà bây giờ n là Successor(k) cho n lưu giữ. Việc chuyển khóa sẽ do tầng trên của ứng dụng thực hiện. Khi một node chuẩn bị rời khỏi mạng, nó cần thông báo cho các node bên cạnh biết để ổn định lại mạng. Node đó cũng sẽ chuyển các khóa nó lưu giữ cho node Successor của nó. 1.4 Kết luận Chúng ta vừa tìm hiểu tổng quan về mạng ngang hàng, qua đó ta thấy những nhược điểm của mạng ngang hàng thuần túy đã được khắc phục khá hiệu quả bởi mạng ngang hàng có cấu trúc nhờ vào việc áp dụng những kiến trúc DHT. Tuy nhiên, một trong những vấn đề trọng tâm cần giải quyết trong mạng DHT là làm thế nào để cân bằng tải giữa các node tham gia trong hệ thống. Yếu tố gây mất cân bằng tải trước hết là khả năng không giống nhau của các node 21 tham gia vào mạng và một số yếu tố khác cũng dẫn tới việc mất cân bằng tải trong mạng, như việc lựa chọn định danh ngẫu nhiên của các node và của dữ liệu hoặc các nguyên nhân khác như tính phổ biến của các file dẫn đến tình trạng một số node phải chịu truy vấn nhiều hơn, trong khi một số node khác lại bị ít truy vấn. Những vấn đề còn tồn tại trong mạng DHT và các hướng giải quyết luận văn xin tiếp tục trình bày ở các chương sau. 22 CHƯƠNG 2 - CÂN BẰNG TẢI TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC Cân bằng tải là một trong những điều kiện để giúp cho mạng có thể hoạt động một cách có hiệu quả. Có rất nhiều các nguyên nhân dẫn đến mất cân bằng tải và đã có một số nghiên cứu và đã có các giải pháp cho vấn đề cân bằng tải. Trong chương này xin trình bày các nghiên cứu về một số nguyên nhân dẫn đến mất cân bằng tải và một số giải pháp cân bằng tải đã được công bố. 2.1 Khái niệm về tải trên mạng ngang hàng 2.1.1 Khái niệm Mục đích chính của các hệ thống P2P là chia sẻ tài nguyên sẵn có (bandwidth, storage, CPU power) giữa các peers sao cho người dùng có thể truy vấn và sử dụng một cách hiệu quả. “Hiệu quả” ở đây nghĩa là hệ thống phải đảm bảo sự phân chia “tải” càng đồng đều giữa các peers càng tốt  cân bằng tải là vấn đề rất quan trọng đối với hệ thống P2P. Tải (Load/Workload ): phụ thuộc vào từng hệ thống P2P cụ thể: - Số bit yêu cầu để lưu trữ dữ liệu. - Băng thông mạng. - Lượng thời gian mà CPU cần để xử lý công việc… Các kí hiệu: n – số nodes trong hệ thống. li – tải của ni tại một thời điểm cụ thể. ci – Khả năng tải (capacity) của node của ni, µi – hệ số sử dụng (utilization) của node ni. i i i c l Khi µi > 1, node n bị “nặng tải”, ngược lại node n được coi là “nhẹ tải”.   n nodes n n nodes n c l  µ – Hệ số sử dụng của hệ thống (system utilization). 23 2.1.2 Node quá tải Khả năng tải của một node (C,Target): Là tải lớn nhất mà một node có thể nhận được. Với mỗi nút ni mà tải thực tế tại thời điểm bất kỳ vượt quá khả năng chịu tải lớn nhất của nó thì nút ni gọi là quá tải (Overloaded). Một nút quá tải không có khả năng lưu trữ, định tuyến, hoặc tính toán…. 2.1.3 Node có tải cao và Node có tải thấp Như đã trình bày ở trên mỗi nút chỉ có một khả năng tải Ci nào đó. Theo lý thuyết khi một nút có tải chưa vượt quá Ci vẫn chưa bị coi là quá tải. Tuy nhiên trong thực tế khi các nút hoạt động cần phải có những xử lý tải trung gian (temporarily) do vậy tải có thể vượt quá khả năng tải Ci. Vì lý do đó mà ta đưa ra khái niệm nút có tải cao và nút có tải thấp. Mỗi nút được thiết lập ngưỡng tải cao Ui và ngưỡng tải thấp Li. Tuy nhiên việc xem xét nút có tải cao và nút có tải thấp còn phụ thuộc vào từng thuật toán cụ thể. 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 Bên cạnh ưu điểm trong việc tổ chức và truy vấn dữ liệu một cách có cấu trúc, các giao thức sử dụng DHT có một nhược điểm tồn tại và đã được đề cập trong nhiều nghiên cứu, đó là: Sự phân tán dữ liệu giữa các nút trong hệ thống. Dựa trên tính chất phân bố ngẫu nhiên kết quả của hàm băm, khi tính toán đến độ phức tạp của truy vấn hay phép gán dữ liệu trên DHT, người ta thường mặc định là dữ liệu phân bố gần như đồng đều giữa các nút. Bên cạnh đó, các nút tham gia hệ thống cũng được coi là có khả năng như nhau về băng thông, lưu trữ, xử lý của CPU… Trong thực tế lại có một sự khác biệt lớn về tải giữa các nút hay còn gọi là sự mất cân bằng tải. Có thể có nhiều nguyên nhân dẫn tới việc mất cân bằng tải trên mạng ngang hàng, ở đây luận văn xin đưa ra bốn nguyên nhân chính dẫn đến mất cân bằng tải. 2.2.1 Định danh các node không cân bằng Do định danh được chọn một cách ngẫu nhiên nên mỗi nút phải chịu quản lý một vùng với số lượng files dữ liệu được gán khác nhau (Thông thường các vùng lớn hơn sẽ được gán số lượng files dữ liệu nhiều hơn). Trong những hệ thống lớn với giải thuật sinh ra ID cho các nút mà không có tình trạng sung đột 24 - node - data thì sự khác nhau về kích cỡ của vùng nhỏ nhất và lớn nhất có thể lên tới O(NlogN). Hình 7. Định danh các node không cân bằng 2.2.2 Định danh dữ liệu không cân bằng Giả sử vấn đề định danh node đã được giải quyết, nếu dữ liệu được phân bố quá tập trung vào một vùng thì cũng sẽ gây tình trạng “nặng tải” tại khu vực đó. Nói cách khác, vị trí đặt files cũng có thể gây ảnh hưởng lớn tới hiệu năng của hệ thống. Hình 8. Dữ liệu các node không cân bằng Kết quả mô phỏng hệ thống DHT Chord ở hình 9 với 4,096 node và khoảng 500,000 files dữ liệu cho thấy không có sự phân bố tối ưu dữ liệu trên các node (hình trái), thậm chí mô phỏng với số files dữ liệu dao động từ 100,000 tới 1,000,000 đã cho thấy một số node không hề phải chịu trách nhiệm quản lí bất cứ một chút tải nào (hình phải). 25 Hình 9. Kết quả mô phỏng về sự phân bố dữ liệu không đều nhau 2.2.3 Hot spots Một số nghiên cứu đã cho thấy mức độ thường xuyên truy vấn đến các files có thể dao động từ 1 – 3 lần. Các tác giả đã phát hiện ra rằng trong các hệ thống P2P hiện nay chỉ có 10% số các files được truy vấn nhiều nhất và chiếm tới 60% tổng lưu thông trên mạng. Ví dụ các dữ liệu mà được nhiều người yêu thích (các file MP3 được nhiều người truy cập) và dẫn đến việc truy cập vào nút này nhiều hơn, do đó nó phải chịu tải nhiều hơn các node bình thường khác. Hình 10. Node Host spots britney.mp3 tallat-song1.mp3 tallat-song2.mp3 tallat-song3.mp3 tallat-song4.mp3 - node - data 26 2.2.4 Khả năng các node không cân bằng Trong thực tế các nút tham gia vào mạng thường rất đa dạng và có khả năng (CPU, Storage, Bandwidth) là khác nhau, có những node khi tham gia vào mạng là những máy tính đời cũ kết nối Internet chậm (Dial Up), nhưng cũng có những máy tham gia vào mạng là các máy có cấu hình mạnh kết nối internet băng thông rộng(ADSL). Saroui và đồng nghiệp đã nghiên cứu 2 hệ thống chia sẻ files nổi tiếng là Napster và Gnutella cho thấy mức độ chênh lệch về khả năng của các node có thể lên tới 3, thậm chí là 5 lần. Trong một thực tế như vậy, nếu các vùng mà được gán cho các node yếu thì cho dù phân bố lưu trữ các files dữ liệu và truy vấn trong hệ thống đạt được sự đồng đều thì vẫn xảy ra sự mất cân bằng tải nghiêm trọng. Hình 11.Khả năng các nút không cân bằng 2.2.5 Nhận xét Với những nguyên nhân đã nêu ở trên thì rõ ràng việc phân tán tải đồng đều trên hệ thống không thể chỉ đơn giản dựa vào các hàm băm. Những kĩ thuật khác nhằm mục đích cân bằng tải giữa các node cần được đưa vào áp dụng. 2.3 Các giải pháp cân bằng tải Đã có nhiều nghiên cứu về cân bằng tải được các tác giả đưa ra cho hệ thống mạng P2P dựa trên DHT. Nói chung, các giải pháp này được phân thành hai hướng chính: hướng tiếp cận dựa trên server ảo (virtual server) và hướng tiếp cận không dựa trên server ảo. Trong mục này luận văn xin được trình bày về một số thuật toán theo hai hướng tiếp cận trên. - node - data 27 2.3.1 Hướng sử dụng server ảo Theo hướng này mỗi node vật lý quản lý một hoặc nhiều server ảo với các định danh ngẫu nhiên được chọn từ không gian định danh. Các server ảo hoạt động như các node tham gia mạng DHT. Trong một hệ thống với các node có khả năng đồng đều cao, mỗi node vật lý cần duy trì O(logn) server ảo để làm giảm nhân tố mất cân bằng xuống đến một hằng số. Với một hệ thống DHT gồm nhiều node có khả năng chịu tải khác nhau, mỗi node vật lý sẽ chọn một số lượng server ảo tỷ lệ với khả năng của nó. Sau đây luận văn xin trình bày một số thuật toán cân bằng tải thực hiện theo hướng này. a. Sử dụng Log(N) Virtual Servers Tư tưởng của giải thuật cân bằng tải này khá đơn giản, đó là: sử dụng log(N)VS[4] cho mỗi node để cân bằng các không gian định danh node. Giải thuật này được xây dựng dựa trên thực tế là các định danh node không được phân bố một cách đồng đều trên toàn bộ không gian định danh mà có phân bố rất gần với dạng phân bố Poisson. Log(N) VS mặc định tải được phân bố trong không gian định danh một cách đồng đều và khả năng các node là như nhau. Chính vì vậy, nếu mỗi node có 1 VS thì dẫn tới khả năng một số node sẽ gặp phải tình trạng “nghẽn cổ chai” (nguyên nhân mất cân bằng tải thứ nhất đã nêu ở trên). Theo Lí thuyết giới hạn trung tâm (Central Limit Theorem), nếu số lượng VS của mỗi node càng tăng lên thì các định danh node được phân bố đồng đều hơn trong không gian định danh. Điều này đồng nghĩa với việc mức độ cân bằng tải trong hệ thống càng cao hơn. Tuy nhiên, việc mỗi node vật lí có quá nhiều VS sẽ dẫn tới việc tăng thông tin quản trị nên giải thuật này đã đưa ra giải pháp là mỗi node sẽ có log(N) VS. Ví dụ minh họa ở hình 12 cho thấy, trong quá trình ra nhập mạng, mỗi node tự hình thành một số VS và mỗi VS ra nhập hệ thống một cách độc lập. 28 Hình 12.Cân bằng tải sử dụng Log(N) Virtual Servers Đánh giá: Log(N) VS đơn giản và hoạt động tốt với giả thiết rằng sự phân bố về tải là đồng đều nhau và các node có khả năng như nhau. Tuy nhiên, việc tăng thêm số lượng VS sẽ làm nảy sinh một số vấn đề. Thứ nhất, khi các node ra/vào mạng thường xuyên, chúng phải mang theo các VS của node đó và sẽ dẫn tới mất log(N) lần điều chỉnh. Thứ hai, mỗi node phải tăng thêm log(N) lần việc lưu trữ thông tin quản trị VS cũng như thông tin tìm kiếm. Bên cạnh đó, số bước tìm kiếm cũng tăng lên khi hệ thống có nhiều VS hơn. b. Phương pháp Proportion Giải thuật Proportion[4] đề cập tới việc giải quyết vấn đề các nút tham gia hệ thống có khả năng khác nhau. Với giải thuật này, khi tham gia vào mạng mỗi nút vật lý sẽ tạo ra một số lượng các VS tuỳ theo khả năng của nút. Bên cạnh đó, thông tin về tải trước đó cũng được tính đến. Sau bước đầu tiên này, mỗi nút sẽ tự tính toán việc thêm hoặc bớt tải mà không liên hệ với bất cứ node nào khác Mỗi node sau khi đã tham gia hệ thống sẽ định thời chạy thuật toán Proportion-Adjust để tự tạo mới hoặc loại bỏ một số VS. Nếu một node đã quá tải và đang có nhiều hơn 1 VS, nó sẽ chọn VS chịu tải ít nhất có thể làm cho node trở thành nhẹ tải để loại bỏ (dòng 2-3 của giải thuật ). Nếu một node là nhẹ tải, nó sẽ tạo thêm 1 VS nếu điều đó không làm nó trở thành nặng tải (dòng 4-6). Hình 13 mô tả một cách trực quan quá trình loại bỏ hay tạo mới VS của một node. PROPORTION-ADJUST() 1 (Initially create VSs in proportion to capacity ) 2 if overloaded and VSset.size > 1 3 then Delete VS that will best unload us 29 4 if underloaded and . WW U VSet size   5 and VSset.size < VSset.maxsize 6 then Create VS.id  h(x + VSset.size ) Hình 13. Tạo mới VS (a) và loại bỏ VS (b) Đánh giá: Thuật toán Proportion cho phép các node có khả năng khác nhau khi tham gia vào hệ thống có thể linh hoạt điều chỉnh tải cho mình, điều đó giúp thực hiện việc cân bằng tải cho hệ thống. Tuy nhiên, việc các node độc lập thực hiện điều chỉnh tải có một số nhược điểm. Trước hết, một node chỉ với một vài VS thì không thể đánh giá một cách chính xác về hiệu quả của việc tạo ra 1 VS mới. Bên cạnh đó, nếu một node quá tải và loại bỏ 1 VS của nó thì điều này có thể gây nên tình trạng nặng tải với các node khác và dẫn tới việc phải loại bỏ hàng loạt VS. Cuối cùng, khi toàn hệ thống đang ở tình trạng nhẹ tải, thuật toán sẽ dẫn tới việc tất cả các node tạo ra số lượng tối đa VS cho phép, điều này sẽ làm tăng đáng kể số bước tìm kiếm hoặc tình trạng mất ổn định khi các node ra khỏi mạng (vì khi một node rời mạng thì các VS của nó sẽ bị loại bỏ). c.Phương pháp di chuyển Virtual Server (Transfer) Giải thuật Transfer[4] hướng vào việc điều chỉnh tải của các node trong hệ thống theo phương pháp “động”. Nguyên tắc của giải thuật này như sau: Mỗi node vật lí chọn một số lượng nhất định các định danh và mỗi định danh sẽ được dành cho một VS. Các node nặng tải sử dụng thuật toán Transfer liên hệ với các node nhẹ tải để yêu cầu được di chuyển một phần tải của mình (thực chất là gán lại VS giữa các node này). Giả sử gọi node h là nặng tải, node l là nhẹ tải. Việc di chuyển các VS v giữa các node phải thỏa mãn các ràng buộc sau: 1. Việc di chuyển v từ h sang l không làm cho l thành node nặng tải. 2. v là VS “nhẹ nhất” có thể di chuyển để h trở thành nhẹ tải. 30 3. Nếu không có VS nào có thể di chuyển để h trở thành nhẹ tải thì di chuyển VS “nặng nhất” từ h sang l. Thuật toán Transfer được minh họa tại Hình 14 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) TRANSFER() 1 if !overloaded 2 then return 3 if VSset.size > 1 4 then Contact node n at random 5 Choose v  VSset such that: 6 (a) Transferring v to n will not overload n 7 (b) v is the least loaded virtual server 8 that will halt overload; 9 Failing that, let v be most loaded VS 10 else v  VSset [0] 11 Create VS.id is ( ( ), ). 2 d t pred v vv id  mod D 12 TRANSFER Giải thuật Transfer có 03 phương pháp di chuyển VS, đó là: “one-to-one”, “one-to-many”, “many-to-many”[2]. Phương pháp One – to – One Phương pháp đầu tiên dựa trên quan hệ 1-1, 2 nút được lấy một cách ngẫu nhiên. Một server ảo dịch chuyển được khởi tạo nếu như một nút là chịu tải nặng nút còn lại chịu tải nhẹ. 31 Hình 15. Phương pháp One - to - One Phương pháp này dễ dàng thực hiện trong một mô hình phân tán. Mỗi nút chịu tải nhẹ có thể định kỳ lấy 1 ID ngẫu nhiên rồi sau đó thực hiện thao tác tìm kiếm để tìm ra nút chịu trách nhiệm với ID đó. Nếu nút đó là nút chịu tải nặng thì một sự dịch chuyển có thể thực hiện giữa 2 nút. Trong phương pháp này chỉ có nút chịu tải nhẹ mới thực hiện thăm dò; Nút tải nặng không thực hiện bất cứ thăm dò nào. Đặc điểm của phương pháp này: - Các nút tải nặng được giảm bớt sức nặng của việc thăm dò. - Khi một hệ thống tải rất nặng và hầu hết các nút chịu tải nặng không có sự nguy hiểm nào cho việc tải của mạng khác hoặc bị thất bại. - Nếu tải của một nút tương ứng với độ dài của không gian ID mà nút đó sở hữu một đầu dò ngẫu nhiên sẽ được thực hiện bởi nút tải nhẹ để tìm ra nút tải nặng. Phương pháp One – to – Many Không giống như phương pháp đầu tiên phương pháp này cho phép tại một thời điểm 1 nút tải nặng xem xét nhiều hơn một nút tải nhẹ. Lấy h biểu thị cho nút tải nặng và lấy l1, l2,.....,lk là một tập các nút tải nhẹ được xem xét bởi h. với mỗi cặp (h,li) chúng ta lấy một server ảo vi. Chọn nút tải nhẹ nhất mà làm cho nút h tải nhẹ, nếu không có server như vậy số lượng các server vi (1≤i≤k) được dịch chuyển. Chúng ta thực hiện phương pháp này bằng việc duy trì các Directory mà lưu trữ thông tin tải về một tập các nút tải nhẹ trong hệ thống. Sử dụng hệ thống DHT giống nhau để lưu trữ các Directory này. Giả sử rằng có d Directory trong hệ thống. Một nút tải nhẹ l được băm vào một Directory bằng việc sử dụng một hàm băm tốt h’ mà cho ta giá trị trong đoạn [0,d). Một Directory i được lưu trữ tại nút chịu trách nhiệm với ID h(i), ở đó h là một hàm băm khác. 32 Hình 16. Phương pháp One - to - Many Một nút chịu tải nhẹ l sẽ thông báo định kỳ tới tải đích và tải hiện tại để nút i=h(h’(l)), nút chịu trách nhiệm cho Directory h’(l). Lần lượt, các nút tải nặng sẽ định kỳ lấy mẫu các Directory đang tồn tại. Một nút tải nặng n lấy ngẫu nhiên k[0,d] và gửi thông tin về tải đích của nó và tải của tất cả các server ảo tới nút j=h(h’(k)). Ở trên nhận như là một thông báo, nút j như là nút chịu tải nhẹ trong Directory của nó, để tìm ra server ảo tốt nhất mà có thể dịch chuyển từ n tới một nút chịu tải nhẹ trong Directory của nó. Quá trình xử lý này sẽ lặp lại cho đến khi tất cả các nút trở thành tải nhẹ. Phương pháp Many – to – Many Phương pháp này là sự mở rộng của hai phương pháp trên. Trong khi phương pháp thứ nhất chúng ta thấy phù hợp với một nút chịu tải nặng và một nút chịu tải nhẹ, ở phương pháp thứ 2 phương pháp phù hợp với một nút chịu tải nặng và nhiều nút chịu tải nhẹ, trong phương pháp này chúng ta thấy nó phù hợp với nhiều nút chịu tải nặng và nhiều nút chịu tải nhẹ. Phương pháp này cho phép nhiều nút chịu tải nặng và nhiều nút chịu tải nhẹ tương tác lẫn nhau, chúng ta sử dụng khái niệm “Global pool” của các server ảo, một bước trung gian di chuyển các server ảo từ một nút chịu tải nặng tới một nút chịu tải nhẹ. “Pool” là một cấu trúc dữ liệu được sử dụng để tính toán vị trí cuối cùng; không có tải nào thực sự bị di chuyển cho đến khi thuật toán kết thúc. Đánh giá: Một ưu điểm quan trọng của giải thuật này là sự linh hoạt trong việc di chuyển VS từ node này sang node khác (không chỉ giới hạn ở các node hàng xóm). Bên cạnh đó, giải thuật cũng rất phù hợp với việc sử dụng bảng băm phân tán vì việc di chuyển VS cũng giống như việc một node vào (join) hay ra khỏi 33 (leave) hệ thống DHT. Tuy nhiên, phương pháp này bộc lộ 02 nhược điểm quan trọng. Thứ nhất, việc duy trì các Directory D ở các node vật lí làm mất đi một đặc điểm quan trọng của hệ thống đó là tính phân tán vì thực chất một số nodes phải liên hệ với Directory D để lấy thông tin theo hình thức “tập trung” (tương tự như Client/Server). Trong trường hợp node chứa Directory D gặp sự cố, vấn đề cân bằng tải của khu vực này chắc chắn sẽ bị ảnh hưởng nghiêm trọng. Thứ hai, node chứa Directory D là xác định, ít thay đổi nên đây chính là điểm yếu dễ bị tấn công, và hậu quả tương nhự như ở nhược điểm thứ nhất, vấn đề cân bằng tải không thể thực hiện được Nhận xét Qua việc phân tích và đánh giá về các giải thuật cân bằng tải tiếp cận theo hướng sử dụng server ảo luận văn nhận thấy, giải pháp sử dụng server ảo còn tồn tại một số yếu điểm, chẳng hạn như để quản lý được các server ảo thì mỗi node phải duy trì khá nhiều liên kết đến các server ảo đó, thông thường số liên kết này là O(logn). 2.3.2 Hướng không sử dụng server ảo Theo hướng này mỗi định danh trong không gian địa chỉ sẽ tương ứng với một node vật lý trong mạng. Để đạt được sự cân bằng trong hệ thống các giải pháp đưa ra đều phải dịch chuyển định danh của các node trong hệ thống khi có một node tham gia hoặc rời khỏi hệ thống. Một thuật toán điển hình đi theo hướng này đó là cân bằng tải theo ngưỡng. Thuật toán cân bằng tải theo ngưỡng Thuật toán cân bằng tải theo ngưỡng luôn duy trì được tải của mỗi node dưới một ngưỡng  nào đó. Một node trong mạng sẽ cố gắng chuyển tải cho các node khác khi tải của nó tăng quá ngưỡng . Xét một dãy các ngưỡng i iT c    với i ≥ 1 và c là một hằng số nào đó. Khi tải của một node vượt quá ngưỡng Tj, node đó sẽ khởi tạo thuật toán cân bằng tải theo ngưỡng. 34 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. Ý tưởng của thuật toán cân bằng tải theo ngưỡng được mô tả như sau: khi tải của một node n trong mạng vượt quá một ngưỡng Tj nào đó thì đầu tiên nó cố gắng chuyển tải cho một trong hai láng riềng có tải nhỏ hơn. Nếu cả hai láng riềng đều có tải lơn hơn và không thể nhận được tải nữa thì nó tìm một node nhẹ tải trong mạng và có tải nhỏ nhất, nhờ node này nhận tải hộ bằng cách dịch chuyển định danh của node nhẹ tải vừa tìm được vào giữa node n và predecessor của n. Để tìm một node nhẹ tải, node n phát một thông điệp hỏi successor của n, successor của n tính toán tải của nó và gửi trả lời node n nếu nó thỏa mãn điều kiện node nhẹ tải có thể dịch chuyển được. Ngược lại, successor của n phát tiếp thông điệp để hỏi node tiếp theo trong vòng Chord (node tiếp theo theo chiều kim đồng hồ). Quá trình này tiếp tục cho đến khi tìm được một node nhẹ tải thỏa mãn điều kiện, hoặc là duyệt hết các node mà không tìm được node nào thỏa mãn. Đã có một số tác giả đề xuất phương pháp cân bằng tải theo hướng này, cụ thể là: Theo tác giả H. Feelif, M. Kitsuregawa, and B. C. Ooi: Khi tải của một Node trong hệ thống vượt quá một ngưỡng nào đó thì nó thực hiện việc cân bằng tải theo các bước sau: a). Xác định tải của các láng riềng của nó để chọn ra láng riềng có tải nhỏ hơn. b). Chuyển tải của nó sang láng liếng có tải nhỏ vừa tìm được ở bước a. Tiếp tục áp dụng việc cân bằng tải cho các Node láng riềng. 35 B B 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 Theo tác giả Prasanna Ganesan Đưa ra một cải tiến dựa vào phương pháp cân bằng tải theo ngưỡng: Tác giả thấy rằng: nếu các Node láng riềng có tải cao thì việc cân bằng tải khi hệ thống đạt đến mức độ cân bằng thì lượng tải di chuyển trong hệ thống sẽ nhiều hơn khi định danh lại thứ tự các Node. Nếu một trong 2 Node láng riềng có thể nhận được tải thì nó sẽ chuyển tải cho Node láng riềng đó. 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 36 Nếu các Node láng riềng không nhận được tải thì nó sẽ đi tìm Node có tải thấp nhất trong hệ thống và nhờ Node đó chịu tải hộ. 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 Giải pháp này tải giữa các Node được di chuyển thực sự. Tác giả Jonathan Ledlie Sử dụng ý tưởng của các tác giả: H. Feelif, M. Kitsuregawa, and B. C. Ooi và Prasanna Ganesan đã giới thiệu ở trên. Tác giả có hai cải tiến - Sử dụng khái niệm Utilization (Hệ số sử dụng) thay cho Workload bởi vì thuật toán ban đầu đã giả thiết các nút có khả năng tải giống nhau. - Các nút chỉ thực hiện việc cân bằng tải khi chúng tăng thêm đến một mức nào đó. 37 Mỗi nút cho duy nhất một VS, các ID đã chọn ngẫu nhiên khi khởi tạo. Thuật toán cân bằng tải được thực hiện theo các bước ở trên. Với thuật toán này nó thực hiện cân bằng tải cho một node với VS là v vào thời điểm t. Các nút thiết đặt giá trị Unitization hiện tại của mình đến khi tăng đến một mức nào đó. Khi một node đó tăng đến một ngưỡng . Nếu Level của một nút tăng lên thì nó bắt đầu thực hiện cân bằng tải, trước hết nó sẽ xem xét nhờ các hàng xóm của mình để nhờ chịu tải hộ, trước tiên VS v sẽ xem xét điều chỉnh với Successor và Predecessor. Nếu như Predecessor nhẹ tải hơn so với v, ID của nó sẽ được dịch chuyển về phía v, như vậy v được giảm tải. v cũng có thể di chuyển ID của nó về phía Predecessor khi đó tải của v được chuyển cho Successor chịu tải hộ. Trong trường hợp các hàng xóm không chịu tải hộ được, nó sẽ đi tìm một node nhẹ tải trong hệ thống và di chuyển nút đó tới cạnh v để giảm tải cho v nhưng với điều kiện khi nút mà có thể chịu tải hộ cho v di chuyển đi thì nó không làm cho successor của nút đó quá tải. 38 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 Theo giải pháp này - Tải của các Node không được di chuyển mà chỉ là di chuyển định danh của các Node. (Mục đích của cân bằng tải là cân bằng số Query truy vấn đến các Node) - Số lượng các thông báo phát ra để đi tìm một Node nhẹ tải tối thiểu là Log(N) thông báo. - Vì là chọn ngẫu nhiên Log(N) định danh nên chưa chắc đã tìm được Node có tải nhẹ thỏa màn điều kiện dịch chuyển. Đánh giá: Các thuật toán cân bằng tải theo ngưỡng hoạt động hiệu quả khi trong mạng có tỷ lệ số node nặng tải so với số node nhẹ tải là thấp. Trong trường hợp này node nặng tải thường chuyển tải ngay cho các node láng riềng, do đó tải truy vấn để tìm node nhẹ tải giảm đáng kể. Ngược lại, khi tỷ lệ trên cao, các node trong mạng hầu hết đều quá tải, khả năng chuyển tải của node quá tải cho láng riềng hầu như không xảy ra, chính vì vậy tải truy vấn đề tìm node nhẹ tải tăng rất nhanh. Chính điều này làm cho hệ thống đạt độ cân bằng chậm, thuật toán không hiệu quả trong trường hợp này. Một nhược điểm nữa của thuật toán này là nó giả sử rằng khả năng của các node tham gia hệ thống là như nhau, trong thực tế khả năng của các node tham gia mạng là không đồng đều nhau, có node mạnh, có node yếu. Do đó, thuật toán cũng không hiệu quả trong trường hợp này. 39 2.3.3 Kết luận Trong chương này luận văn đã trình bày về khái niệm cân bằng tải, tìm hiểu về các nguyên dẫn đến mất cân bằng tải và nghiên cứu hai hướng giải pháp cho cân bằng tải, trong đó có sự đánh giá các giải thuật này. Với việc nghiên cứu những nội dung trên là cơ sở để chúng tôi đưa ra đề xuất cải tiến thuật toán cân bằng tải theo ngưỡng được trình bày ở chương 3. 40 CHƯƠNG 3 - ĐỀ XUẤT CẢI TIẾN THUẬT TOÁN CÂN BẰNG TẢI THEO NGƯỠNG Như đã nêu ở trên, mạng ngang hàng có cấu trúc sử dụng giải thuật Bảng băm phân tán (Distributed Hash Table – DHT). Một vấn đề rất quan trọng trong mạng DHT đó là cân bằng tải. Đã có nhiều nghiên cứu đưa ra các giải pháp để giải quyết vấn đề này. Một số tập trung vào việc cân bằng không gian định danh làm cho khoảng cách giữa các node trở nên đồng đều. Tuy nhiên giải pháp này chỉ tốt trong điều kiện lý tưởng. Các nhà nghiên cứu đã chỉ ra rằng các phân bố truy vấn là không đồng đểu, sự vào ra của các node là ngẫu nhiên và khả năng lưu trữ của các node khác nhau là cũng rất khác nhau. Giải pháp cân bằng tải theo ngưỡng được trình bày trong chương 2 thực hiện cân bằng tải khá tốt, tuy nhiên với phương pháp này ta nhận thấy còn có một số tồn tại như sau: - Số lượng các thông báo phát ra để đi tìm một Node nhẹ tải tối thiểu là Log(N) thông báo. - Vì là chọn ngẫu nhiên Log(N) định danh nên chưa chắc đã tìm được Node có tải nhẹ thỏa mãn điều kiện dịch chuyển. Trên cơ sở nghiên cứu giải pháp cân bằng tải theo ngưỡng chúng tôi đề xuất Giải pháp cân bằng tải theo ngưỡng cải tiến, trong giải pháp của chúng tôi đề xuất giảm bớt số lượng các thông báo phát ra để đi tìm một nút nhẹ tải. Và có phương pháp chọn Node nhẹ tải thoả mãn điều kiện dịch chuyển một cách có hiệu quả hơn. Giải pháp đề xuất của chúng tôi có 2 điểm khác biệt so với các thuật toán đã có : 1) Chúng tôi nghiên cứu thuật toán cân bằng tải theo ngưỡng do Ganesan [9] đưa ra và khái niệm Directory được sử dụng trong các thuật toán cân bằng tải có sử dụng server ảo từ đó đề xuất một thuật toán cân bằng tải mới hoạt động hiệu quả hơn trong các hệ thống dựa trên DHT. 2) Nếu như các thuật toán đề xuất trước đây thường không xem xét đến tải xử lý các câu truy vấn thì. Thuật toán của chúng tôi đề xuất mới này có xem xét đến cả tải xử lý các câu truy vấn tìm kiếm một node trong quá trình thực hiện cân bằng tải. Khi hệ thống đạt đến mức độ cân bằng, số lượng các câu truy vấn để tìm kiếm một node là khá nhiều. 41 3) Ngoài ra, chúng tôi nghiên cứu các đặc điểm của mạng P2P trong thực tế mà các tác giả đã đưa ra: sự ra vào của các node, khả năng của các node và sự phân bố dữ liệu của các node để áp dụng vào hệ thống của chúng tôi. 3.1 Một số khái niệm Xét hệ thống gồm n node vật lý (các máy tính hoặc các thành phần trong một hệ thống P2P). Node ni có khả năng tải cố định là Ci, tương ứng với số lượng tối đa các câu truy vấn mà node đó có thể xử lý. Tại một thời điểm cụ thể, node ni có một tải làm việc (work load) Wi (số câu truy vấn phải xử lý). Hệ số sử dụng ui của một node là tỷ lệ giữa tải làm việc trên khả năng tải của nó: ui = Wi / Ci. Hệ số sử dụng  của toàn bộ hệ thống là tỷ lệ của tổng tải làm việc của các node trên tổng khả năng tải của các node: nnode n nnode n W C    Khi un > 1, ta nói node n là quá tải; trong trường hợp ngược lại node n được gọi là nhẹ tải. Một node quá tải sẽ không có khả năng lưu trữ thêm các đối tượng dữ liệu, xử lý các câu truy vấn hoặc thực hiện việc tính toán, tùy thuộc vào từng ứng dụng cụ thể mà sử dụng khái niệm nặng tải và nhẹ tải để chỉ các node có hệ số sử dụng cao và thấp. Trong hệ thống có một số node đặc biệt gọi là thư mục (directory). Thư mục là node chứa thông tin về các node nhẹ tải có thể di chuyển được. Một node nhẹ tải n được gọi là di chuyển được nếu định danh của n dịch chuyển sang một vị trí khác nằm ngoài khoảng không gian định danh n đến successor của n mà không làm successor của node n quá tải. 3.2 Thuật toán ThresholdPlus Ý tưởng đề xuất thuật toán của chúng tôi  Không sử dụng Server ảo  Sử dụng ý tưởng của Prasanna Ganesan cho vấn đề thực hiện cân bằng tải.  Sử dụng khái niệm Directory của A. Rao vào việc lưu trữ các Node nhẹ tải 42 Như đã giới thiệu ở phần trước thuật toán cân bằng tải theo ngưỡng khi mà một node quá tải nó sẽ đi tìm các node nhẹ tải ở các Directory và để tìm được node nhẹ tải thì thuật thời gian tìm kiếm phải mất tối thiểu Log(N) thông báo. Thuật toán ThresholdPlus của chúng tôi nghiên cứu và đề xuất trên cơ sở của thuật toán Threshold được cải tiến ở cách thức tìm kiếm node nhẹ tải phù hợp và hiệu quả. Thuật toán của này được mô tả chi tiết, gồm ba bước như sau: Bước 1: Node nhẹ tải thông báo cho các thư mục Trong hệ thống có một số node có chức năng làm node để lưu trữ thông tin về các node nhẹ tải có thể dịch chuyển được, node này được gọi là thư mục (Directory), các node này được chọn một cách ngẫu nhiên từ hệ thống, cơ chế lựa chọn các node làm thư mục như sau: Giả sử hệ thống có d thư mục, d là một số rất nhỏ so với số node vật lý trong hệ thống. Thư mục i sẽ được lưu ở node chịu trách nhiệm quản lý định danh D(i), trong đó D là một hàm băm ánh xạ mỗi giá trị i trong khoảng [0,d) vào một định danh trên vòng Chord một cách ngẫu nhiên. Định kỳ trong khoảng thời gian nhất định, các node sẽ chạy thuật toán kiểm tra tải của mình. Nếu một node có định danh L kiểm tra thấy mình là nhẹ tải, nó sẽ gửi một thông điệp tới hỏi successor của mình xem nếu khi chuyển sang định danh khác có làm cho node successor hoặc predecessor quá tải hay không?. Nếu không làm quá tải cho các node này thì node L có thể di chuyển được, khi đó node L sẽ gửi thông báo chứa thông tin của nó cho node phụ trách thư mục i, trong đó i = h(L), h là hàm băm ánh xạ định danh của node L vào một giá trị trong khoảng [0,d) . Hay nói cách khác, node L sẽ gửi thông báo chứa thông tin tải của nó đến node phụ trách định danh D(h(L)). Hình vẽ 22 minh họa hệ thống gồm hai thư mục 43 Hình 22. Các node nhẹ tải A và F hỏi successor của nó (các đường mũi tên nét liên) và thông báo tình trạng tải cho thư mục 1 và thư mục 2 (các đường mũi tên nét đứt). Bước 2: Chia sẻ tải cho các node láng giềng Trong bước này, giả sử một node n trong hệ thống bị quá tải, quá trình nó thực hiện cân bằng tải diễn ra như sau: Đầu tiên node quá tải n sẽ kiểm tra xem hai node láng giềng của mình là (predecessor của n và successor của n) có khả năng nhận tải được hộ được hay không. Nếu được node n sẽ kiểm tra xem một trong hai láng riềng, láng riềng nào có tải thấp hơn nó sẽ thực hiện chia của mình cho node đó. Hình vẽ 23 và 24 mô tả quá trình chia sẻ tải của node nặng tải cho các node láng riềng. 44 Hình 23. Node A thực hiện cân bằng tải, node láng riềng B nhận tải hộ node A bằng cách dịch chuyển định danh về phía A Hình 24. Node A thực hiện cân bằng tải, node A chia tải cho node láng giềng C bằng cách dịch chuyển định danh của A về phía B. Bước 3: Định danh lại một node Trong trường hợp hai láng giềng của n không thể gánh hộ tải cho node n thì node n sẽ chọn ngẫu nhiên một thư mục(Directory) i và gửi một thông điệp tới node phụ trách thư mục đó để tìm kiếm một node nhẹ tải. Thư mục i sẽ xem xét vào yêu cầu giảm tải (chia tải) của node nặng tải và khả năng của các node nhẹ tải có trong thư mục để chọn ra một node nhẹ tải thích hợp nhất gửi cho node n. Node nhẹ tải này phải đảm bảo tính chất: + Nhận được tải cho node nặng tải mà không bị quá tải + Khả năng của node nhẹ tải là tốt nhất trong số các node nhẹ tải có thể nhận tải hộ được node nặng tải. Dựa trên thông tin trả lời từ thư mục i, node n sẽ yêu cầu node nhẹ tải mà nó biết dịch chuyển định danh về vị trí giữa predecessor(n) và n để chịu tải hộ node n. Nếu không tìm được node nhẹ tải nào thỏa mãn, node n sẽ hỏi các thư mục còn lại. Hình vẽ 25 mô tả quá trình này. 45 Hình 25. Node A hỏi thư mục 1 để tìm một node nhẹ tải có thể dịch chuyển được (đường mũi tên nét liên). Định danh của node nhẹ tải E được chuyển đến giữa predecessor(A) và A để nhận tải hộ node A (đường mũi tên nét đứt). Nhận xét Thuật toán ThresholdPlus của chúng tôi đề xuất có hai điểm khác biệt so với các thuật toán trước đó: Thứ nhất: Nếu như thuật toán Threshold nguyên thủy, để một node nặng tải tìm một node nhẹ tải thì node nặng tải phải đòi hỏi nhiều nhất (N-1) node (N là số node vật lý trong hệ thống) để tìm thấy một node nhẹ tải. Thuật toán ThresholdPlus chúng tôi đề xuất sử dụng thư mục để chứa các node nhẹ tải có thể dịch chuyển được (tức là khi node này di chuyển đi sang vị trí khác không làm quá tải đến các node bên cạnh). Thư mục đảm bảo chắc chắn rằng khi trong hệ thống còn có một node nhẹ tải có thể di chuyển được thì node thực hiện quá trình cân bằng tải bao giờ cũng tìm được node nhẹ tải đó một cách nhanh chóng. Thứ hai: Thư mục trong thuật toán ThresholdPlus chỉ chứa các node nhẹ tải có thể di chuyển được do đó số lượng node nhẹ tải trong thư mục quản lý ít hơn nhiều so với số server ảo nhẹ tải trong các thuật toán cân bằng tải dịch chuyển server ảo có sự dụng khái niệm thư mục. Chính điều cải tiến này làm giảm đáng kể việc quản lý liên kết đến các node nhẹ tải trong hệ thống. 46 Thuật toán được mô tả như sau: THRESHOLDPLUS(v,t) 1 Các node nhẹ tải thông báo tình trạng tải cho thư mục 2 v.levelt  ngưỡng của node v tại thời điểm t 2 if v.levelt ≤ v.levelt-1 then 3 return 4 v’  láng riềng với ngưỡng nhỏ nhất 5 if v’.levelt < v.levelt then 6 chuyển tải từ v sang v’ 7 else 8 Hỏi thư mục để tìm node có tải nhẹ 9 s  node có tải nhỏ nhất 10 Chuyển định danh của s vào giữa Pred(v) và node v 3.3 Đánh giá: Số thông báo mà giải pháp Threshold Plus của chúng tôi đề xuất phát ra để tìm kiếm một node nhẹ tải sẽ chỉ là hai thông báo, một thông báo gửi cho Directory và một thông báo gửi lại từ Directory vì giải pháp này sử dụng Directory chỉ lưu trữ các Node nhẹ tải có thể dịch chuyển được. Trong khi đó các thuật toán đã đề xuất Directory lưu trữ toàn bộ các node nhẹ tải do đó mà phải mất nhiều thông báo phát ra để đi tìm node nhẹ tải thỏa mãn. Các node nhẹ tải trong hệ thống trước khi gửi thông tin của mình cho Directory nó sẽ hỏi Successor của nó trước xem nếu nó di chuyển đi chỗ khác thì Successor có bị quá tải không. Nếu nó bị quá tải thì Node nhẹ tải đó sẽ không gửi thông tin cho Directory do vậy, Directory sẽ không phải quản lý nhiều liên kết tới các Node nhẹ tải. Việc tìm kiếm một Node nhẹ tải chỉ mất hai thông báo, nhanh hơn rất nhiều so với các phương pháp trên. Do đó, số lượng thông báo trong hệ thống sẽ giảm đáng kể. Ngoài những ưu điểm được kể ra ở trên giải pháp của chúng tôi cũng còn những nhược điểm sau: + Làm tăng tải cho node được chọn làm thư mục: Node được chọn làm thư mục ngoài việc phải xử lý các câu truy vấn thông thường còn phải xử lý các câu truy vấn tìm node nhẹ tải. Tuy nhiên như đã trình bày, node thư mục chỉ chứa một số rất ít các thông tin về node nhẹ tải có thể di chuyển được, do đó nó không ảnh hưởng nhiều đến khả năng xử lý của node thư mục. 47 + Phải xử lý việc mất mát dữ liệu khi có một node thư mục rời hệ thống: khi một node thư mục rời hệ thống, thông tin về các node nhẹ tải mà nó lưu sẽ bị mất. Để đảm bảo tính sẵn sàng của thông tin, thông tin về các node nhẹ tải sẽ được lưu ở node successor của node thư mục. Theo giao thức Chord, khi một node rời mạng, successor của nó sẽ quản lý các thông tin nằm trong khoảng định danh mà nó để lại. Như vậy, khi một node thư mục rời hệ thống, successor của nó sẽ trở thành node thư mục mới và các node trong hệ thống sẽ đăng ký thông tin cho node thư mục mới này. 48 CHƯƠNG 4 - ĐÁNH GIÁ HIỆU QUẢ CỦA GIẢI PHÁP ĐỀ XUẤT DỰA TRÊN MÔ PHỎNG Phần này chúng tôi xin mô tả kết quả từ các thí nghiệm được cài đặt với thuật toán ThresholdPlus và so sánh với thuật toán Threshold của Ganesan và một số thuật toán khác đã đề cập trong luận văn. Trong thí nghiệm mô phỏng này chúng tôi lựa chọn 10 thư mục và lưu trữ ở 10 node ngẫu nhiên trong mạng gồm 4096 node vật lý. Mô phỏng hoạt động theo thời gian rời rạc và sử dụng các tham số đầu vào của J. Ledlie. Mỗi bước thời gian gồm ba kịch bản: node tham gia và rời hệ thống, cập nhật bảng tìm đường, truy vấn dữ liệu và thực hiện cân bằng tải. Node vào và ra: Tại mỗi bước các node vào và ra hệ thống tuân theo phân bố xác suất Pareto. Dựa trên phân bố xác suất này chúng tôi tạo ra một file theo dõi mạng trong một khoảng thời gian t xác định. Trong khoảng thời gian đó thời điểm vào, ra của một node được ghi lại trong một file. Cập nhật bảng tìm đường: Mỗi node mới tham gia vào hệ thống với một bảng tìm đường rỗng. Các node này dựa theo cơ chế Chord để tìm một node để thực hiện việc điền log(n) hàng trong bảng tìm đường . Truy vấn dữ liệu: Truy vấn được khởi tạo giống nhau từ các node được chọn ngẫu nhiên. Điểm đến của các câu truy vấn được chọn theo phân bố Uniform hoặc phần bố Zipf phụ thuộc vào từng thí nghiệm cụ thể. Mỗi hop trong câu truy vấn sử dụng một finger thích hợp để chuyển câu truy vấn tới đích. Mỗi khi một node được dùng để chuyển câu truy vấn (dữ liệu hoặc tìm một node khác) đến đích, duy trì bảng tìm đường thì một đơn vị tải được cộng thêm vào node đó. Nếu một hop tại đó câu truy vấn được chuyển tiếp có tải vượt quá khả năng của nó thì câu truy vấn đó được gọi là không thành công. Một câu truy vấn được gọi là thành công nếu nó đến được node đích. Cân bằng tải: Các node sẽ kiểm tra cân bằng tải của chúng trung bình khoảng 30 giây một lần. Nếu chúng mất cân bằng thì thuật toán cân bằng tải sẽ được gọi để thực hiện việc cân bằng tải. Dưới đây là một số kết quả mô phỏng. 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. Thí nghiệm đầu tiền mà chúng tôi thực hiện là xem xét khả năng thích ứng của các thuật toán cân bằng tải khi thời gian sống trung bình của một node biến 49 đổi. Chúng tôi tạo ra các file theo rõi sự ra, vào của các node trong mạng với thời gian sống trung bình của các node được xét là 15 phút, 30 phút, 1 giờ, 2 giờ và 4 giờ. Mỗi lần chạy thí nghiệm, khả năng của một node trong mạng được giữ cố định, mỗi node được khởi tạo trung bình 10 câu truy vấn trong một giây. Truy vấn được tạo ra dưới dạng Uniform và Zipf với tham số =1.2. Kết quả của thí nghiệm được vẽ trong hình vẽ 26. Kết quả của thí nghiệm cho thấy với số truy vấn trung bình 10 truy vấn/node, thuật toán ThresholdPlus có tỷ lệ thành công lớn hơn thuật toán Threshold khoảng 9% đối với truy vấn dạng Uniform và khoảng 14% đối với truy vấn dạng Zipf. Hình 26. Thời gian sống trung bình của một node thay đổi, các câu truy vấn thực hiện với phân bố Zipf và Uniform. 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. Thí nghiệm thứ hai mà luận văn kiểm tra xem các thuật toán cân bằng tải làm việc như thế nào khi số câu truy vấn phát ra từ các node tăng lên trong hệ thống. Trong đánh giá này chúng tôi giữ cố định khả năng của các node và thời 50 gian sống trung bình của một node trong mạng là 2 giờ trong các lần chạy thí nghiệm và thay đổi số lượng các câu truy vấn đặt vào một node. Các câu truy vấn phát ra cũng được phân bổ dưới dạng Uniform và dạng Zipf với  =1.2. Kết quả thí nghiệm được thể hiện trong hình vẽ 27 và cho thấy thuật toán ThresholdPlus mà chúng tôi đề xuất có khả năng thích nghi tốt hơn thuật toán Threshold khoảng 6% đối với truy vấn dạng Uniform và khoảng 10% đối với truy vấn dạng Zip. Hình 27. Số câu truy vấn đặt vào một node thay đổi, truy vấn được phân bố ở dạng Zipf và Uniform. 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 Trong thí nghiệm thứ ba chúng tôi đánh giá ảnh hưởng của câu truy vấn dạng Zpif tới các thuật toán cân bằng tải. Các tham số khả năng của các node trong mỗi lần chạy thí nghiệm được giữ không đổi, thời gian sống trung bình của một node 51 trong mạng là 2 giờ. Truy vấn phân bố cho các node ở dạng Zipf với tham số  thay đổi ( = 0.8, 1.2, 2.4 và 4.8). Kết quả thí nghiệm được thể hiện trong hình 28. Với kết quả này cho thấy với số truy vấn trung bình 10 truy vấn/node, thuật toán của chúng tôi có tỷ lệ thành công lớn hơn thuật toán Threshold khoảng 5%. Hình 28. Truy vấn đặt vào các node ở dạng phân bố Zipf với tỷ lệ thay đổi. 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ó: Trong thí nghiệm tiếp theo chúng tôi so sánh thuật toán cân bằng tải của tôi đề xuất với các thuật toán: Tranfer, proportion Trong đánh giá này chúng tôi giữ cố định khả năng của các node và thời gian sống trung bình của một node trong mạng là 2 giờ trong các lần chạy thí nghiệm và thay đổi số lượng các câu truy vấn đặt vào một node. Các câu truy vấn phát ra cũng được phân bổ dưới dạng Uniform và dạng Zipf với  =1.2. Kết quả của thí nghiệm được vẽ trong hình 29 cho thấy thuật toàn Tranfer và proportion có tỷ lệ truy vấn thành công khá giống nhau, tuy nhiên Tranfer có tỉ lệ cao hơn một chút, thuật toán của chúng tôi đề xuất có tỷ lệ thành công lớn hơn khoảng 7% so với hai thuật toán trên ở phân bố dạng Uniform, khoảng 6% ở phân bố Zipf. 52 Hình 29. So sánh ThresholdPlus với Tranfer và Propotion. 4.5 Kết luận Mô phỏng của chúng tôi đã thử nghiệm kiểm và đánh giá thuật toán trên các tình huống: Ảnh hưởng thời gian sống của một node tới các thuật toán, Ảnh hưởng của số lượng các câu truy vấn tới các thuật toán và Ả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, bằng thực nghiệm chúng tôi đã so sánh giải pháp của chúng tôi với các phương pháp đã có là Tranfer và 53 proportion các câu truy vấn phát ra phân bổ dưới dạng Uniform và dạng Zipf. Kết quả của mô phỏng cho thấy phương pháp cân bằng tải của chúng tôi đề xuất cho tuỷ lệ truy vấn thành công cao hơn so với phương pháp cân bằng tải theo thuật toán Threshold , thuật toán Tranfer, proportion. 54 CHƯƠNG 5 - KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 5.1 Kết luận Báo cáo luận văn đã tìm hiểu và giới thiệu tóm tắt tổng quan về mạng ngang hàng, các mô hình mạng ngang hàng đặc biệt trình bày về mạng ngang hàng có cấu trúc sử dụng bảng băm phân tán DHT mà điển hình là mạng Chord. Với mạng ngang hàng có cấu trúc, hiện nay một vấn đề đang được các nhà nghiên cứu quan tâm đó là vấn đề Cân bằng tải, luận văn đã tìm hiểu về các khái niệm cân bằng tải trên mạng ngang hàng, các nguyên nhân dẫn tới việc mất cân bằng tải trên mạng ngang hàng đồng thời cũng đã nêu ra và phân tích một số phương pháp, kỹ thuật cân bằng tải trên mạng ngang hàng đã có. Chúng tôi đã nghiên cứu một số thuật toán cân bằng tải trong mạng ngang hàng có cấu trúc và đề xuất một thuật toán cải tiến thuật toán cân bằng tải theo ngưỡng sử dụng cấu trúc thư mục. Các thay đổi chính mà thuật toán của chúng tôi đưa ra là: Thứ nhất, thuật toán của chúng tôi xem xét cả tải truy vấn các node trong quá trình thực hiện cân bằng tải. Thứ hai, thuật toán của chúng tôi tìm chính xác và nhanh chóng được một node nhẹ tải cho quá trình thực hiện cân bằng tải mà số thông điệp phát ra chỉ tính bằng hằng số. Các thuật toán cân bằng tải của các tác giả khác hoặc là không quan tâm đến tải truy vấn node hoặc là cần phải thực hiện khoảng N thông điệp truy vấn để tìm một node nhẹ tải. Sau khi cài đặt, chạy thử nghiệm và đánh giá kết quả, chúng tôi thấy rằng trong điều kiện mạng gần với thực tế (khả năng của các node không giống nhau, các câu truy vấn đặt vào các node không đồng đều, thời gian sống của các node không giống nhau) thuật toán của chúng tôi hoạt động tốt hơn so với thuật toán cân bằng tải theo ngưỡng do Ganesan đề xuất. 5.2 Hướng phát triển tiếp theo Tiếp theo, chúng tôi dự định nghiên cứu các vấn đề quan trọng sau đây: Truy vấn trong khoảng. Thuật toán mà chúng tôi đề xuất cải tiến chỉ hoạt động trong môi trường mạng mà các câu truy vấn là chính xác. Có nghĩa là câu truy vấn phát ra từ một node với yêu cầu tìm chính xác một dữ liệu nào đó. Vấn đề tìm kiếm dữ liệu trong một khoảng nào đó cũng đã được một số tác giả 55 nghiên cứu và đưa ra nhiều giải pháp. Cân bằng tải cho các câu truy vấn tìm kiếm trong khoảng cũng là một vấn đề quan trọng đặt ra cần giải quyết. Nâng cao hiệu quả hoạt động của thư mục trong giải thuật cân bằng tải. Như đã giới thiệu, thư mục là nơi lưu tữ thông tin về các node nhẹ tải phục vụ cho quá trình cần bằng tải. Nếu vần đề an ninh an toàn cho thư mục không được đảm bảo sẽ ảnh hưởng lớn đến thực hiện cân bằng tải. Ngoài ra nghiên cứu việc chọn số lượng thư mục cho phù hợp cũng đặc biệt quan trọng, nếu số thư mục được chọn mà ít thì thông tin tập trung vào thư mục quá nhiều dẫn tới thư mục bị quá tải và không được hiện được yêu cầu đặt ra, ngược lại thư mục chọn nhiều quá thì việc quản lý các thư mục và tìm kiếm node thỏa mãn để thực hiện cân bằng tải cũng mất nhiều thời gian hơn và khó khăn hơn. 56 TÀI LIỆU THAM KHẢO [1] I. Stoica, R. Morris, D. Karger, M.F. Kaashoek, H. Balakrisnan, “Chord: A Scalable peer-to-peer lookup service for Internet applications”, In Proceedings of ACM SIGCOMM’01, August 2001 [2] Ananth Rao, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp, and Ion Stoica. Load Balancing in Structured P2P Systems. In Proceedings IPTPS, 2003. [3] P. B. Godfrey and I. Stoica., Heterogeneity and Load Balance in Distributed Hash Table. Proceedings of IEEE INFOCOM, 2005: p. 596-606. [4] J. Ledlie and M. Seltzer, Distributed, Secure Load Balancing with Skew, Heterogeneity, and Churn. Proc. IEEE INFOCOM, 2005. [5] D. R. Karger and M. Ruhl., Simple efficient load balancing algorithms for peer-to-peer systems. In Proc.of IPTPS, 2004. [6] Y. Zhu and Y. Hu., Efficient, proximity-aware load balancing for DHT- based p2p systems. IEEE Transactions on Parallel and Distributed Systems, 2005. VOL 16(4). [7] J. Byers, J.C., and M. Mitzenmacher, Simple Load Balancing for Distributed Hash Tables. In Proc. of 2nd International Workshop on Peer-to-Peer Systems (IPTPS ’03), Berkeley, USA, February 2003. [8] Gerhard Weikum, “Peer-to-Peer Information Systems”, dbs.cs.uni-sb.de/lehre/ws03_04/P2P-seminar.htm [9] P.Ganesan, M. Bawa, H. G Molina, Online Balancing of Range-Partitioned Data with Application to Peer-to-Peer Systems. Proceeding of the 30th VLDB Conference Toronto, Canada, 2004 [10] F. Bustamante and Y. Qiao. Friendships that last: Peer lifespan and its role in P2P protocols. In Eighth International Workshop on Web Content Caching and Distribution, Hawthorne, NY, October 2003.