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

đượ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.