(A) Một Mạng Chord Với 6 Node, 5 Item Và N=16. (B) Nguyên Tắc Chung Của Bảng Routing

1.1.3. Ứng dụng p2p

Các ứng dụng p2p có thể chia vào bốn nhóm:

Chia sẻ file (file sharing): lưu trữ và chia sẻ nội dung là ứng dụng thành công nhất của công nghệ p2p. Các ứng dụng chia sẻ file tập trung vào việc lưu trữ thông tin trên các peer khác nhau trên mạng và lấy thông tin từ các peer đó. Các ứng dụng thuộc nhóm này bao gồm Napster, Gnutella, Freenet, Kazaa, Chord, ….

Tính toán phân tán (distributed computing): các ứng dụng thuộc nhóm này sử dụng tài nguyên từ các máy tính được nối mạng. Ý tưởng chính của các ứng dụng tính toán phân tán là các chu kỳ xử lý nhàn rỗi trên bất kỳ máy tính nối mạng nào đều có thể được sử dụng cho việc giải quyết bài toán trên các máy yêu cầu nhiều năng lực tính toán. SETI (Search for Ex-traterrestrial Intelligence) là một dự án nghiên cứu khoa học nhằm mục đích xây dựng một máy tính ảo khổng lồ từ sức mạnh của các máy tính nối mạng trong chù kỳ nhàn rỗi của chúng.

Cộng tác (collaboration): các ứng dụng cộng tác p2p cho phép người sử dụng cộng tác với nhau ở mức ứng dụng. Các ứng dụng này rất đa dạng, từ instant messaging, chat đến game online hay các ứng dụng chia sẻ sử dụng trong thương mại, giáo dục hay môi trường gia đình.

Platform (nền): các platform p2p cung cấp hạ tầng hỗ trợ các ứng dụng sử dụng cơ chế p2p. Các thành phần p2p được sử dụng bao gồm naming, discovery, communication, security và resource aggregation. JXTA là một p2p platform cung cấp hạ tầng tính toán và lập trình mạng.

1.1.4. Các vấn đề đối với mạng p2p hiện nay

Các hệ thống p2p có nhiều ưu điểm so với các hệ thống client-server truyền thống như tính khả mở, khả năng chịu lỗi, hiệu năng. Tuy nhiên các hệ thống p2p đang phải đối mặt với một số vấn đề:

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

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

Bảo mật (security): các cài đặt phân tán phát sinh thêm một số vấn đề bảo mật so với kiến trúc client-server truyền thống. Bởi vì trong hệ thống p2p các peer là động và không tin tưởng lẫn nhau nên để đạt được mức bảo mật cao trong các hệ thống p2p sẽ khó hơn trong các hệ thống client-server. Các cơ chế bảo mật truyền thống để bảo vệ dữ liệu và hệ thống khỏi tấn công, xâm nhập như firewall không thể bảo vệ thống p2p bởi vì các hệ thống này phân tán và các cơ chế bảo mật có thể ngăn chặn, hạn chế quá trình truyền thông p2p. Do đó cần đưa ra các khái niệm bảo mật mới cho phép tương tác và xử lý phân tán trong các hệ thống p2p.

Tính tin cậy (reliability): một hệ thống tin cậy là một hệ thống có khả năng hồi phục sau khi xuất hiện lỗi. Các cơ chế đảm bảo độ tin cậy trong mạng p2p bao gồm nhân bản dữ liệu, phát hiện và khôi phục node bị lỗi, xây dựng nhiều cơ chế đảm bảo thông tin định vị, tránh “single point of failure” và đảm bảo nhiều đường đi tới dữ liệu.

Tính linh hoạt (flexibility): một trong những tính chất quan trọng nhất trong các hệ thống p2p là các peer tự chủ, chúng có thể join/leave bất kỳ lúc nào. Các hệ thống p2p gần đây có quy mô lớn, điều khiển phân tán và hoạt động trong môi trường động. Để giải quyết vấn đề quy mô và tính động của các hệ thống p2p, khi xây dựng các hệ thống p2p cần chú ý đến khả năng điều chỉnh và tự tổ chức.

Cân bằng tải (load balancing) : vấn đề phân tán dữ liệu và tính toán rất quan trọng đối với hiệu quả hoạt động của các mạng p2p. Một trong những giải pháp cho vấn đề phân tán này là distributed hash table (DHT). Trong cách tiếp cận này, cân bằng tải được xem xét trên hai khía cạnh: cân bằng không gian địa chỉ tức là cân bằng phân phối của không gian key address trên các node và cân bằng item trong trường hợp phân phối của các item trong không gian địa chỉ không thể là ngẫu nhiên. Cân bằng tải giữa các node tính toán trong hệ thống p2p cũng có thể được cài đặt sử dụng mô hình tự tổ chức dựa trên agent.

1.2. Lý thuyết về Distributed Hash Table (DHT)

1.2.1. Hash Table (bảng băm)

Một hash table là một cấu trúc dữ liệu ánh xạ giữa key và value. Tức là tương ứng với một key, hash table sẽ trả về một value. Để thực hiện việc ánh xạ, hash table sử dụng hash function tính toán vị trí lưu value dựa trên key. Hash function phải đảm bảo: tránh xung đột và dễ dàng thực hiện. Tránh xung đột nghĩa là ánh xạ giữa không gian key và không gian địa chỉ phải đều và ngẫu nhiên đến mức có thể.

1.2.2. Distributed Hash Table

Distributed Hash Table (DHT) là thuật toán được sử dụng trong các ứng dụng p2p, DHT cho phép quản lý mạng p2p theo đúng nghĩa với độ tin cậy cao, khả mở, hiệu quả và có khả năng chịu lỗi.

DHT là một hash table được cài đặt như một hệ thống phân tán. Cũng như một hash table thông thường, DHT cung cấp ánh xạ từ key đến value. Nhưng không giống như hash table thông thường, các value trong một DHT được lưu trên các node khác nhau trong mạng chứ không phải lưu trong một cấu trúc dữ liệu cục bộ. Thông qua một key, value tương ứng được lưu tại một node phù hợp trên mạng hoặc được lấy về từ node tương ứng trên mạng.

Trong một DHT, key được tính ra từ value. Tất cả các key đều nằm trên cùng một không gian địa chỉ. Các ứng dụng file sharing thường sử dụng không gian địa chỉ 160 bit. Để xác định node nào lưu value nào, mỗi node phải có một ID trong không gian địa chỉ giống như không gian địa chỉ của key. Các DHT đưa ra khái niệm khoảng cách giữa hai ID (một key có thể xem như ID của value). Khi đó value được lưu trên node có ID gần với ID của value nhất.

Để lưu một value trên mạng, một node gửi thông điệp yêu cầu lưu dữ liệu tới một contact phù hợp được chọn ra từ bảng routing table, trong bảng routing table,

contact này có ID gần với ID của dữ liệu cần lưu nhất. Quá trình cứ tiếp tục như vậy, thông điệp được chuyển tiếp trên mạng cho đến khi nó gặp node có ID gần với ID của dữ liệu nhất và value được lưu trên node này.

Để tìm một value, thủ tục cũng tương tự, node cần tìm dữ liệu sẽ gửi đi thông điệp tìm kiếm dữ liệu. Sau quá trình chuyển tiếp thông điệp giống như quá trình chuyển tiếp thông điệp lưu dữ liệu, node lưu dữ liệu sẽ được tìm ra và node này sẽ trả dữ liệu cho node tìm kiếm.

Distributed Hash Tables có các ưu điểm khác biệt so với dịch vụ hướng Client- Server truyền thống:

 DHT cho phép hoạt động phân tán, không cần duy trì một server trung tâm để điều khiển hoạt động của mạng p2p. Cũng vì vậy, các ứng dụng p2p sử dụng DHT là các ứng dụng p2p thuần túy.

 Hệ thống có tính khả mở, nghĩa là hệ thống vẫn hoạt động tốt ngay cả với số lượng node và lưu lượng trên mạng lớn.

 Tải được cân bằng giữa các peer trong mạng

 Hệ thống dựa trên giả định rằng mạng không tĩnh và các thay đổi xuất hiện thường xuyên với các node join vào mạng và leave khỏi mạng (còn gọi là churn)

 Việc định tuyến và lấy dữ liệu nhanh và có thể hoàn thành trong thời gian tỷ lệ loga

 Hệ thống mạnh mẽ, nghĩa là nó có thể đứng vững ngay cả khi bị tấn công trên diện rộng

DHT cung cấp dịch vụ lưu trữ, tìm kiếm dữ liệu thông qua hai hàm insert và lookup.

Hình 1.3. Distributed Hash Table

1.3. Giới thiệu một số DHT

Trong phần này chúng ta sẽ xem xét một số well-known DHT như Chord, Kelips, Tapestry, Kademlia. Ta phân tích các DHT này dựa trên một số khía cạnh như sau:

Overlay Graph (sơ đồ mạng overlay): đây là tiêu chuẩn chính để phân biệt các hệ thống với nhau. Đối với mỗi overlay graph, chúng ta sẽ xem xét graph và bảng định tuyến của mỗi node trong graph.

Mapping Items Onto Nodes (ánh xạ giữa item và node): đối với mỗi overlay graph, chúng ta quan tâm đến mối quan hệ giữa ID của node và ID của các item lưu trên node đó, tức là một item cụ thể sẽ được lưu trên node nào.

Lookup process (tiến trình tìm kiếm): tiến trình tìm kiếm trên một mạng diễn ra như thế nào và hiệu năng của quá trình tìm kiếm liên quan chặt chẽ đến loại overlay graph của mạng đó.

Joins, Leaves và Maintenance (gia nhập, rời khỏi mạng và duy trì) : chúng ta sẽ xem một node mới được thêm vào graph như thế nào và một node rời graph như thế nào. Do các node trong mạng thường xuyên join, leave nên cần có một số tiến trình

maintenance để xử lý các thay đổi trong mạng, chúng ta quan tâm đến các tiến trình này diễn ra như thế nào và chi phí thực hiện các tiến trình này.

Replication và fault tolerance (nhân bản và chịu lỗi): bên cạnh các node rời khỏi mạng có báo trước, một số node có thể đột ngột rời khỏi mạng do một số nguyên nhân như mất điện, đường truyền hỏng, …, trường hợp này khó xử lý hơn trường hợp các node thông báo đến các node khác trước khi rời khỏi mạng. Replication là một giải pháp cho trường hợp các node rời khỏi mạng mà không báo trước.

Upper services và applications (ứng dụng và dịch vụ bên trên): một số ứng dụng và dịch vụ đã được phát triển sử dụng DHT.

Implementation (cài đặt): liệt kê một số cài đặt của các DHT.

1.3.1. Chord

Overlay graph

Chord sử dụng một không gian ID vòng tròn kích thước N. Một node Chord với ID là u có một con trỏ tới node đầu tiên đứng sau nó trong không gian ID theo chiều kim đồng hồ, ký hiệu là Succ(u) và một con trỏ tới node đứng trước nó trong không gian ID, ký hiệu là Pred(u). Các node tạo thành một danh sách liên kết hai chiều.

Bên cạnh đó, một node Chord lưu M = log2(N) con trỏ gọi là các finger. Tập các finger của node Chord u được xác định như sau Fu = {(u, Succ(u + 2i−1))}, 1 ≤ i ≤

M. Với cách lựa chọn finger thế này, tong mạng Chord, các node quan sát không gian ID vòng như là không gian này bắt đầu từ ID của chúng. Đồng thời với cách lựa chọn finger của Chord, không gian ID sẽ được chia đôi, nửa thứ nhất cũng được chia đôi, rồi phần tư thứ nhất lại được chia đôi, …

XHình 1.4X cho thấy một mạng với không gian ID N = 16, mỗi node có M=log2(N)= 4 finger. Mạng có các node với ID lần lượt là 0, 3, 5, 9, 11, 12. Cách xây

dựng bảng finger table được thể hiện trong XHình 1.4(X b) . Node n chọn các finger của nó bằng cách xem nó như là điểm khởi đầu của không gian ID, rồi chọn finger là successor của các ID n + 20, n + 21, n + 22, và n + 23. ID cuối cùng n + 23chia không gian ID thành hai phần bằng nhau, ID trước đó n + 22chia nửa thứ nhất thành hai phần bằng nhau, ID n + 21chia phần tư đầu tiên thành hai phần bằng nhau, tương tự ID n + 20chia phần tám thứ nhất thành hai phần bằng nhau. Tuy nhiên, có thể không có node có ID giống với ID tại điểm chia, khi đó successor của ID tại điểm chia được chọn làm finger. XHình 1.4X(c) cho thấy bảng định tuyến của node 3 và node 11.

Hình 1.4. (a) Một mạng Chord với 6 node, 5 item và N=16. (b) Nguyên tắc chung của bảng routing table. (c) Bảng routing table của node 3 và node 11