Quá Trình Thực Nghiệm Và Phương Pháp Đánh Giá Hiệu Năng

truy vấn đến nhiều contact, hoặc node contact sẽ gửi yêu cầu truy vấn tới các node khác cùng nhóm với nó, hoặc node truy vấn có thể yêu cầu một node khác cùng nhóm với nó thực hiện truy vấn item.

Một node muốn chèn một item mới sẽ sử dụng consistent hashing xem item đó được ánh xạ vào nhóm nào. Sau đó node sẽ gửi yêu cầu chèn dữ liệu tới một contact thuộc nhóm đó, node contact sẽ chọn ngẫu nhiên một node bất kỳ trong nhóm và gửi yêu cầu chèn dữ liệu. Node này sẽ trở thành node lưu item. Nếu yêu cầu chèn dữ liệu không thực hiện được, quá trình gửi lại yêu cầu chèn dữ liệu diễn ra như quá trình gửi lại yêu cầu truy vấn.

1.4. Các phương pháp đánh giá, thử nghiệm mạng P2P

Cộng đồng nghiên cứu peer to peer nói chung sử dụng ba phương pháp để đánh giá, kiểm nghiệm các kết quả nghiên cứu là phương pháp phân tích, phương pháp thực nghiệm và phương pháp mô phỏng.

Trong phương pháp phân tích, người ta đánh giá mô hình toán học của hệ thống. Tuy nhiên phương pháp này chỉ hiệu quả đối với các mô hình đơn giản trong khi các mô hình p2p thực tế thường phức tạp.

Trong phương pháp thực nghiệm, người ta tiến hành thử nghiệm trên hệ thống thật, tuy nhiên các hệ thống p2p có số lượng node rất lớn, nếu thực nghiệm trên hệ thống có quy mô nhỏ thì kết quả sẽ không có ý nghĩa. Đồng thời các thay đổi như thay đổi topology mạng hay thay đổi trong protocol trên các node sẽ khó và tốn nhiều thời gian.

Phương pháp mô phỏng cũng có những hạn chế, tuy nhiên nó khắc phục được những hạn chế của phương pháp phân tích và phương pháp thực nghiệm. Tại thời điểm này, phương pháp mô phỏng không hoàn toàn độc lập với hai phương pháp trên. Nếu có thể, nên sử dụng phương pháp phân tích và chứng minh bằng phương pháp mô phỏng. Tương tự, các kết quả mô phỏng nên được chứng minh bằng thực nghiệm trên

các hệ thống thật. Hiện nay, hầu hết các nghiên cứu về p2p được thực hiện sử dụng phương pháp mô phỏng.

1.4.1. Khảo sát các simulator mô phỏng mạng overlay

Cộng đồng nghiên cứu sử dụng khá nhiều simulator khác nhau, có simulator

đang được phát triển, có simulator không được phát triển tiếp.

Simulator

Ngôn ngữ	Trạng thái	License
P2PSim	C++	Active	GPL
PeerSim	Java	Active	LGPL
Query-Cycle Simulator	Java	Inactive	Apache
Narses	Java	Inactive	GPL-like
Neurogrid	Java	Inactive	GPL
GPS	Java	Inactive	Open-Source, No License
Overlay Weaver	Java	Active	Apache
DHTSim	Java	Active	GPL
PlanetSim	Java	Active	LGPL

Có thể bạn quan tâm!

Xem toàn bộ 98 trang tài liệu này.

Bảng 1.1. Trạng thái phát triển của các simulator

Đặc điểm của các simulator như sau:

Simulator

Kiến trúc	Tính dễ dùng	Tính khả mở (max nodes)
P2PSim	Discrete-event cho mạng P2P có cấu trúc	Rất ít tài liệu	3000 nodes
PeerSim	Query-Cycle hoặc Discrete-event cho mạng không cấu trúc. Có thể mô phỏng node joining, departing và failing.	Chỉ có mô phỏng Query-Cycle là có tài liệu	106 node
Narses	Discrete-event, flow-based topology có thể điều chỉnh	600 node, tùy thuộc vào topology bên dưới	600 node
Overlay Weaver	Giả lập phân tán và	Tài liệu về API và	4000 node

một số giải thuật cho structured overlay	mã nguồn tốt
PlanetSim	Mô phỏng discrete- event, sử dụng API chung.	Có tài liệu về thiết kế và API	100 000 node
Neurogrid	Discrete-event cho mạng không có cấu trúc, có thể chỉnh sửa để sử dụng cho mạng có cấu trúc	Có tài liệu mở rộng trên web	300 000 node

Simulator

Thống kê	Underlying network
P2PSim	Cung cấp một lượng hữu hạn thống kê.	end-to-end time graph, G2 graph, GT-ITM, random, và Euclidean
PeerSim	Có thể cài đặt các component để thống kê dữ liệu	Không được mô hình hóa
Narses	Có hỗ trợ nhưng phải cài đặt	Một số topology
Overlay Weaver	Không thể thu thập thống kê	Không được mô hình hóa
PlanetSim	Không có cơ chế thu thập thống kê nhưng có thể xem trực quan	Một số ít topology
Neurogrid	Cần sửa mã nguồn	Không được mô hình hóa

Bảng 1.2. Đặc điểm của các simulator

1.4.2. P2PSim

P2PSim là phần mềm mã nguồn mở, đa tiến trình, discrete event để mô phỏng mạng overlay có cấu trúc do một nhóm nghiên cứu mạng p2p tại MIT phát triển. P2PSim được nhiều nhóm nghiên cứu sử dụng để nghiên cứu DHT.

P2PSim hỗ trợ đến mô phỏng mạng với số node tối đa là 3000, với nhiều topology khác nhau như end-to-end time graph, G2 graph, GT-ITM, random, và Euclidean. Tuy nhiên tài liệu về P2PSim rất hạn chế.

Luận văn này sử dụng P2PSim để mô phỏng và đánh giá, so sánh hiệu năng giữa các DHT.

Địa chỉ web site của P2PSim : HUhttp://pdos.csail.mit.edu/p2psim/U

Chương 2.

Đ1B

ánh giá hiệu năng một số DHT

2.1. Bài toán thực tế

Hầu hết các DHT được thiết kế để hoạt động với các peer là máy tính. Đây là môi trường có độ ổn định khá cao, tức là khoảng thời gian từ lúc một node gia nhập cho đến khi rời khỏi mạng tương đối dài. Trong môi trường này, các DHT hoạt động với hiệu năng tương đối cao.

Hiệu năng của một DHT được đánh giá thông qua hai tham số chính là tỷ lệ tìm kiếm dữ liệu thành công khi dữ liệu có trên mạng và độ trễ tìm kiếm.

Vài năm trở lại đây các sản phẩm cho người sử dụng có thể nối mạng phát triển hết sức mạnh mẽ và đa dạng, các sản phầm không chỉ có máy tính mà còn có các thiết bị như điện thoại, PDA, tivi, …. Cũng giống như người sử dụng máy tính, người sử dụng các thiết bị này cũng có nhu cầu chia sẻ, khai thác nguồn tài nguyên hết sức phong phú trên mạng p2p, đặc biệt là các tài nguyên như video, audio. Tuy nhiên thời gian kết nối mạng của các thiết bị này thường rất ngắn, thậm chí có thể tính bằng giây, dẫn đến sự bất ổn định của mạng. Các DHT vốn được thiết kế để hoạt động với các peer là máy tính lúc này không đáp ứng được yêu cầu về hiệu năng do khoảng thời gian các peer ở trên mạng quá ngắn. Một mạng như vậy người ta gọi là mạng có churn rate cao.

Một bài toán mới đặt ra cho cộng đồng nghiên cứu p2p là xây dựng các mạng p2p thích nghi được với môi trường churn rate cao. Một trong những giải pháp được nhiều người quan tâm là cải tiến các DHT hiện có để chúng hoạt động hiệu quả ngay cả trong môi trường có churn rate cao. Việc đưa ra được giải pháp cải tiến hiệu năng cần căn cứ vào một số cơ sở, một trong những cơ sở quan trọng là việc đánh giá hiệu năng của các DHT trong môi trường mới.

Luận văn này đánh giá, so sánh hiệu năng của một số well-known DHT, đặc biệt là trong môi trường churn rate cao. Từ kết quả này kết hợp với phân tích lý thuyết, luận văn đưa ra giải pháp cải tiến hiệu năng cho một DHT tiềm năng (Chord) trong điều kiện churn rate cao.

2.2. Đánh giá hiệu năng một số DHT

2.2.1. Mục tiêu và cơ sở lý luận

Phần này của luận văn phân tích, đánh giá hiệu năng của các DHT nhằm tạo cơ sở cho việc đưa ra các giải pháp cải tiến hiệu năng của chúng đồng thời giúp các ứng dụng lựa chọn, sử dụng các DHT hiệu quả hơn.

Đánh giá hiệu năng của các DHT bao gồm nhiều khía cạnh:

 Xác định ngưỡng churn rate mà các DHT hoạt động tốt

 Phân tích ảnh hưởng của tham số thiết kế đến hiệu năng của DHT

 So sánh hiệu năng của các DHT khác nhau

 Đánh giá tính khả mở của các DHT.

Các đánh giá được thực hiện trong dải churn rate rộng từ cao đến thấp, đặc biệt chú trọng đến trường hợp churn rate cao.

Khi churn rate càng cao, độ ổn định của mạng càng thấp thì hiệu năng của các DHT càng giảm. Do đó một trong những nhiệm vụ đầu tiên của phần đánh giá hiệu năng là xác định ngưỡng churn rate mà các DHT hoạt động với hiệu năng cao.

Đánh giá ảnh hưởng của các tham số thiết kế đến hiệu năng một DHT cho phép xác định các tham số quan trọng đối với hiệu năng của DHT và xác định khoảng giá trị của các tham số trong đó DHT làm việc tốt.

So sánh hiệu năng của các DHT khác nhau trong các điều kiện khác nhau cho thấy trong từng điều kiện cụ thê, DHT nào làm việc tốt hơn và tốt hơn ở những khía cạnh nào.

Đánh giá ảnh hưởng của các tham số thiết kế và so sánh hiệu năng của các DHT khác nhau không những có ích trong việc nghiên cứu và cải tiến DHT mà còn cho phép các ứng dụng lựa chọn DHT phù hợp với điều kiện môi trường, điều chỉnh các tham số cần thiết để đạt được hiệu quả tối ưu.

Tính khả mở là một đặc tính quan trọng của DHT, một DHT hiệu quả phải có tính khả mở cao. Kết quả đánh giá tính khả mở của các DHT có thể làm cơ sở để lựa chọn, sử dụng DHT.

2.2.2. Quá trình thực nghiệm và phương pháp đánh giá hiệu năng

Các DHT được mô phỏng với nhiều bộ tham số khác nhau sử dụng phần mềm mô phỏng P2PSim. Quá trình mô phỏng được thực hiện trong nhiều tháng với số lượng mô phỏng lên đến hơn 20 000 để đảm bảo kết quả mô phỏng ổn định.

Ứng với mỗi bộ tham số, kết quả mô phỏng DHT thống kê các thông số hiệu năng của DHT như tỷ lệ tìm kiếm thành công (hoặc tỷ lệ tìm kiếm thất bại), độ trễ tìm kiếm, băng thông trung bình mỗi node sử dụng,….

Các mô phỏng này được biểu diễn trên độ thị hai chiều với trục đứng biểu diễn tỷ lệ tìm kiếm thành công/thất bại, hoặc độ trễ tìm kiếm và trục ngang là băng thông trung bình mỗi node sử dụng. Nói cách khác, trục đứng biểu diễn các thông số hiệu năng và trục ngang biểu diễn chi phí phải bỏ ra để đạt được hiệu năng đó. Rõ ràng, một DHT tốt nếu có tỷ lệ tìm kiếm thành công cao, độ trễ tìm kiếm thấp và băng thông mỗi node sử dụng trung bình thấp.

Kết quả mô phỏng DHT với một bộ tham số đầu vào tương ứng với một điểm trên đồ thị. Khi mô phỏng DHT với nhiều bộ tham số khác nhau, ta có nhiều điểm trên đồ thị.

Hình 2.1X là một đồ thị biểu diễn kết quả mô phỏng giao thức Chord với trục đứng là tỷ lệ tìm kiếm thất bại và trục ngang là băng thông trung bình mỗi node sử dụng.

Việc đánh giá hiệu năng của một DHT, so sánh hiệu năng giữa các DHT dựa trên đường convex hull. Đường convex hull là đường bao nhỏ nhất của một hợp điểm. Ở đây chúng ta chỉ quan tâm đến đoạn gần với hai trục từ điểm có hoành độ cao nhất đến điểm có tung độ cao nhất. Khi trục đứng là tỷ lệ tìm kiếm thất bại hoặc là độ trễ tìm kiếm thì đường này chính là sự kết hợp tối ưu giữa hiệu năng và chi phí.

Có hai loại đường convex hull, đường overall convex hull và đường parameter convex hull. Đường overall convex hull là đường convex hull của tất cả các điểm ứng với tất cả các bộ tham số. P2PSim còn cho phép chỉ biểu diễn các điểm ứng với một giá trị nào đó của một tham số trên đồ thị. Khi đó, đường convex hull của tập điểm này gọi là đường parameter convex hull ứng với tham số đó. Đường overall convex hull được sử dụng để đánh giá hiệu năng tổng quát trong khi đường parameter convex hull được dùng để phân tích ảnh hưởng của các tham số đến hiệu năng của DHT.

Hình 2.1. Node join/leave với interval=600 s trong mạng Chord 100 node

2.2.3. Xác định ngưỡng churn rate các DHT làm việc tốt

2.2.3.1. 4BMục tiêu

Xác định ngưỡng churn rate mà từng DHT còn làm việc với hiệu quả cao, cụ thể là:

 Xác định churn rate mà tỷ lệ tìm kiếm dữ liệu thành công của DHT đạt 90% trở lên cho một số trường hợp tốt.

 Xác định khoảng giá trị của các tham số của DHT trong những trường hợp này

2.2.3.2. 5BPhương pháp xác định ngưỡng

Quá trình tìm ra churn rate cho tỷ lệ tìm kiếm thành công trên 90% trong các trường hợp tốt bao gồm hai quá trình đan xen: quá trình chọn ra churn rate cho hiệu năng cao và quá trình chọn ra dải giá trị tốt của từng tham số.

Việc chọn các trường hợp tốt được thực hiện bằng cách mô phỏng với các tham số nhận giá trị biến thiên trong một dải rộng. Dựa trên các kết quả đạt được, chúng tôi chọn ra các dải giá trị tham số cho kết quả tốt, các giải giá trị này hẹp hơn giải giá trị trong mô phỏng đầu tiên. DHT lại được mô phỏng với giải giá trị này.

Quá trình chọn churn rate bắt đầu bằng mô phỏng DHT với churn rate cao, hiệu năng của DHT trong trường hợp này thấp, tỷ lệ tìm kiếm thành công < 90 % kể cả những trường hợp tốt. Sau đó, DHT lại được mô phỏng với churn rate rất thấp, hiệu năng của DHT trong trường hợp này tốt hơn cả yêu cầu, tỷ lệ tìm kiếm thành công > 90 % cho hầu hết nhiều trường hợp. Dựa trên hai mô phỏng trên, chúng tôi chọn ra churn rate nằm giữa hai churn rate trên và thực hiện mô phỏng. Quá trình chọn churn rate diễn ra như vậy cho đến khi chọn được churn rate cho kết quả > 90 % trong các trường hợp tốt.

Quá trình lựa chọn trên được biểu diễn trong đồ thị