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ữ
Based -DHT
Broadcast
Chord
Ý nghĩa
Dựa trên bảng băm phân tán
Một thông điệp truyền tới tất cả các trạm
Một giao thức dựa trên mang ngang hàng
có cấu trúc
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
Một bản ghi trong bảng dùng để lưu thông
tin về các đặc tả tài nguyên tại mỗi node
Bảng định tuyến
Node được truy cập với tần số cao
Định danh
Entry
Finger Table
Host Ports
Identify
Key
Khóa
LBM (Load Balancing Matrix) Ma trận cân bằng tải
Load
Tải
Load-balancing
Node
Cân bằng tải
Thực thể có khả năng thực hiện một công
việc hữu ích nào đó và trao đổi kết quả với
các thực thể khác qua mạng một cách trực
tiếp hoặc gián tiếp
Overload
Quá tải
P2P (Peer to Peer network)
Partial query
Predecessor(n)
Mạng ngang hàng
Truy vấn từng phần
Node đứng liền sau n (Tính theo chiều kim
đồng hồ)
Query
Truy vấn
Successor(n)
Node đứng liền trước n (Tính theo chiều
kim đồng hồ)
Target
Unilization
Workload
Tải lớn nhất mà một node có thể nhận
Hệ số sử dụng
Tải làm việc
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
Finger[k].start
.interval
Definition
(n+2k-1) mod 2m, 1 ≤ k ≤ m
(finger[k].start, finger[k+1].start
First node ≥ n.finger[k].start
.node
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.
l – tải của n tại một thời điểm cụ thể.
i
i
c – Khả năng tải (capacity) của node của n ,
i
i
µ – hệ số sử dụng (utilization) của node n .
i
i
l
i
i
ci
Khi µ > 1, node n bị “nặng tải”, ngược lại node n được coi là “nhẹ
i
tải”.
l
n
nodesn
nodesn
c
n
µ – 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
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.
- node
- data
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.
tallat-song4.mp3
tallat-song3.mp3
- node
- data
tallat-song1.mp3
tallat-song2.mp3
britney.mp3
Hình 10. Node Host spots
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.
- node
- data
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.
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
2
3
(Initially create VSs in proportion to capacity )
if overloaded and VSset.size > 1
then Delete VS that will best unload us
29
W
4
if underloaded and
W
U
VSet.size
5
6
and VSset.size < VSset.maxsize
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
2
3
4
5
6
7
if !overloaded
then return
if VSset.size > 1
then Contact node n at random
Choose v VSset such that:
(a) Transferring v to n will not overload n
(b) v is the least loaded virtual server
8
that will halt overload;
Failing that, let v be most loaded VS
10 else v VSset [0]
9
dist(pred(v),v)
11
Create VS.id
mod D
v.id
2
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ẹ.
Tải về để xem bản đầy đủ
56 trang
18/05/2025
220
Bạn đang xem 30 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_giai_phap_can_bang_tai_su_dung_cau_truc_thu_muc_cho.pdf
