Kỹ thuật bảng băm phân tán trên mạng ngang hàng giải pháp kiến trú mở và ứng dụng

Hệ thống này đ nh nghĩa liên kếị t gi a các nút mữ ạng trong mạng theo một thuật toán cụ ể, đồng thời xác định chặt chth ẽ ỗ m i nút m ng sạ ẽ chịu trách nhiệm đối với một phần dữ liệu c

Mụ ụ c l c

PHẦN MỞI ĐẦU 3

Nhiệm vụ ủ c a luận văn 6

N i dung luộ ận văn 6

Lời cảm ơn 8

Danh mục thu t ng 9ậ ữ Phần I M NG NGANG HÀNG VÀ CÁC HỆ ỐNG DHTs 10Ạ TH 1.1 H ng ngang hàng 10ệthố 1.1.1 Overlay network 11

1.1.2 Quá trình phát triển của các hệ thố ng P2P 11

1.1.3 Phân loại ứng d ng trên m ng ngang hàng 15ụ ạ 1.1.4 Các ng d ng trêứ ụ n mạng ngang hàng 16

1.2 Tìm hiểu DHT ảng băm phân tán- B 19

1.2.1 DHT là gì? 19

1.2.2 L ch s phát triị ử ển của DHTs 22

1.2.3 Sức mạnh của DHTs 25

1.2.4 Các thu c tính quan tr ng cộ ọ ủa DHTs 29

1.2.5 B o mả ật và xác thực 30

1.2.6 Các thao tác khác của DHT 31

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

1.3.1 Chord [11] 33

1.3.2 Kademlia [16] 39

1.3.3 Tapestry[14] 42

1.4 Kết luận 47

Phần II: BAMBOO DHT VÀ OPENDHT 49

2.1 Bamboo 49

2.1.1 T ng quan v Bamboo 49ổ ề 2.1.2 Ưu điểm của Bamboo DHTs 55

2.1.3 H n ch cạ ế ủa DHTs 56

2.1.4 DHT Geometries (Sơ đồ ủ c a DHT) 58

2.1.5 Hoạt động Lookup 60

2.1.5 DHT Storage 62

2.1.6 DHT chia s ẻgiữa các ứng d ng 63ụ 2.1.7 Chia s mẻ ột DHT giữa các Client 66

2.1.8 Cân b ng t i 66ằ ả 2.2 OpenDHT 68

2.2.1 T ng quan v ổ ềThiết kế 70

2.2.2 Các giao di n 73ệ 2.2.3 Phân b l u tr 83ổ ư ữ 2.2.4 Đánh giá 89

2.2.5 Đánh giá dựa trên vi c tri n khai 94ệ ể 2.3 Kết luận 101

Phần III: ỨNG D NG MINH HỤ ỌA 102

3.1 Mục tiêu của chương trình 102

3.2 Thiết kế 102

3.2.1 Các API đượ ử ục s d ng 105

3.2.2 C u trúc cấ ủa mạng multicast và vi c join vào m ng 106ệ ạ 3.2.3 C ơchế truyền thông điệp 111

3.3 Tri n khai ng dể ứ ụng và đánh giá 112

PHẦN KẾT LUẬN 117

TÓM TẮT NỘI DUNG ĐỀ TÀI 119

Tóm tắt tiếng Việt 119

Tóm tắt tiếng Anh 121

Abstract 121

TÀI LIỆU THAM KHẢO 123

PH Ầ N MỞ Ầ I Đ U

Mạng internet đã làm thay đổi thế giới ới sự ra đời của các trang thông tin, các dịch v

v ụ tìm kiếm, kinh doanh điện tử Nó đã ả… nh hưởng lớ ế ờn đ n đ i sống thường nhật của mọi cư dân trên hành tinh Trên mạng internet người ta có thể đặt vé máy bay, rao bán nhà đất, tìm hướng dẫn ch đư ng hay tìm đọc nhanh nhất các thông tin thờ ựỉ ờ i s quốc

t … ế

Chính sự phát triển và phổ biế ủa các giao dịn c ch internet đã tạo nên những thách thức

mới cho các nhà cung cấp (NCC) dịch vụ NCC phả ải đ m bảo hệ thống vẫ đứng vững n khi có số ợ lư ng ngư i truy cờ ậ ớp l n Những dịch vụ càng thông d ng thì càng phụ ải chịu

đựng đư c lư ng ngượ ợ ời truy c p l n Ví d , m t s trang web tìm ki m ph c v hàng ậ ớ ụ ộ ố ế ụ ụtriệu người tìm kiếm thông tin đồng thời Một đĩa nhạc hay mới phát hành hoặc một phần mềm thông dụng đưa ra một phiên b n m i thì có s lư ng ngư i r t l n truy c p ả ớ ố ợ ờ ấ ớ ậhoặc t i vả ề ừ ộ t m t trang web trong m t thộ ời gian ngắn Muốn vậy h, th ng đó ph i là ệ ố ả

một hệ thống ử lý phân tán, có mộ x t cơ chế quản lý tài nguyên thông minh và có một

s ốkhả năng khác như dưới đây

Đầu tiên, thi t k c a h th ng đó ph i Scalable (khả năng mở ộế ế ủ ệ ố ả r ng v quy mô) Đó là ề

một hệ thống mà kích cỡ ủa hệ thố c ng luôn tương ứng với khả năng đáp ứng của nó

H ệ thống càng mở ộng thì khả năng phục vụ người dùng/số giao dịch càng nhiề Hệ r u

thống cũng không phụ ộc vào t kthu bấ ỳ ộ m t thành phần nào đó, để tránh hiện tượng nghẽ ổn c chai d n đ n giẫ ế ảm hiệu năng của hệ thống và nó cũng tránh cho hệ ố th ng bị

sụp đổkhi thành phần đó b ỗị l Vi ới một hệ thống có thiết kế Scalable thì ta có thể tăng kích cỡ khi khi h thống có nhưu ệ cao hoặc giảm kích cỡ khi hệ thống có nhưu cầu thấp

Thứ hai, h th ng đó phải self-managing (ệ ố khả năng t ự quản lý) H ệthống đó phải có khả năng tự độ ng cân b ng tằ ải, đảm bảo an toàn dữ ệ li u hệ ố th ng Trong trư ng hợp ờnhư trên khi ta tăng kích c cỡ ủa hệ thống thì nó s ph i tự ậẽ ả nh n bi t các thành phần ế

thêm vào và chia sẻ ả t i cho những phần mới thêm đó Ngược lại khi giảm kích cỡ ủ c a

h ệthống thì nó cũng t độự ng khôi phục lại giữ liệu mà phần bị tháo đi đã mang đi Với

một hệ thống lớn và động thì thuộc tính này là hết sức quan trọng

Thứ ba, h th ng đó phải có khả năng ệ ố fault-tolerant (khả năng chịu lỗi) V i m t hớ ộ ệ

thống l n thì ớ x suất xác ảy ra l i t i các bỗ ạ ộ phận là r t lấ ớn, hệ ống v n phth ẫ ải hoạt động

tốt khi số lượng bộ phận bị ỗi nằm trong một tỉ l l ệcho phép

Hiện này, m ng ngang hàng là mạ ột trong nh ng hư ng ti p c n r t t t đ th a mãn các ữ ớ ế ậ ấ ố ể ỏthuộc tính trên Đó là một ki n trúc mà các thành phế ần trong m ng có chạ ức năng và khả năng như nhau Tất cả các máy tham gia đều đóng góp tài nguyên, bao gồm băng thông, lưu trữ, và kh ảnăng tính toán Do đó khi càng nhiều máy tham gia thì khả năng

tổng thể ủa hệ thống mạng càng lớn Tính chất phân tán của mạng ngang hàng giúp ccho mạng hoạ ột đ ng tốt khi m t s máy gộ ố ặp sự ố c

S ựtiến hóa về ấu trúc mạng đã làm cho mạng ngang hàng ngày càng tr c ở lên mạnh mẽ Một trong những cấu trúc đó là DHT (B ng Băm Phân Tán, ti ng Anh: 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 theo một thuật toán cụ ể, đồng thời xác định chặt chth ẽ ỗ 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 ần tìm một c

d ữ liệu, nó chỉ ần áp dụng một giao thứ c 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ả Hiện nay có r t nhiấ ều giải pháp khác nhau để xây dựng một DHT, người ta phân chia các giải pháp đó theo cấu trúc mạng và thuật toán định tuyến Có một số ấ c u trúc n i tiổ ếng bao gồm Chord, CAN, Kademlia, Pastry, Tapestry và Bamboo [10]

Trong luận văn này tôi sẽ trình bày những tìm hiể ủa mình vu c ề ộ m t trong những DHT

nêu trên, đó là Bamboo Nó đư c đánh giá là mợ ột DHT khá mạnh mẽ Giao diện cho các thao ra nhập/rời khỏ ại m ng là khá đơn giản Mỗi node đều có thuật toán duy trì số

ng con tr n các node hàng xóm là hàm logarithmic của kích cỡ ạ m ng, như v y

kích cỡ ạ m ng có thể tăng r t nhanh mà băng thông lưu tr con tr các node hàng ấ để ữ ỏxóm tăng không đáng kể Chi phí cho việc định tuyến, lưu trữ và truy cập cũng được

giới hạn bởi hàm logarithmic c a kích củ ỡ ạ m ng, hơn nữa người ta còn dùng thuật toán

để xác đ nh các node hàng xóm gần nhau về ặị m t vật lý để làm tăng t c đ ố ộliên l c giạ ữa các node Người ta chứng minh mạng vẫn hoạ ột đ ng tốt, không bị ấ m t dữ liệu ngay cảkhi số ợ lư ng node trên mạng bị ỗ l i khá cao ho c tặ ốc độ các nodes tham gia và rời khỏi

mạng cao Cơ chế hoạ ột đ ng của Bamboo là hoàn toàn tự ổ t ch c, tự ứ duy trì Trong triển khai thực t Vế ới ời gian ngắn là 6 phút, có 1000 node trong m ng Bamboo th ạtrong ModelNet vẫn đáp ứng cho các thao tác lấy dữ ệu từ ộli m t node bất kỳ trong vòng ½ giây [1] Bamboo cũng là một hệ thống đáng tin cậy, v i hiớ ệu năng lưu trữ ớ l n

đã triển khai 200-300 nodes trên PlanetLab[1]

OpenDHT [1] là một dịch vụ DHT công c ng đư c thiết kộ ợ ế để ễ d dàng phát triển, triển khai và duy trì các ứng d ng DHT Nó khụ ắc phục đư c như c điợ ợ ểm khó phát tri n cể ủa các ứng d ng DHT truyụ ền thống bằng cách sử ụ d ng một mạng DHT có sẵn để cung

cấp dịch vụ cho nhiều ứng dụng khác nhau Do đó các ứng dụng OpenDHT chỉ ần ctruy cập dịch vụ này thông qua các giao diện đơn giản mà không ph i tri n khai DHT ả ểcho riêng mình Hơn nữa, với các ứng dụng OpenDHT còn cho phép truyền thông vượt qua NAT hoặc Firewall OpenDHT không chỉ ỗ ợ h tr cho các giao di n đơn giản, bảo ệ

mật, nó cũng hỗ mtrợ ột số chức năng phức tạp trong truyền thông bằng cách sử ụ d ng thêm m t sộ ố thư vi n khác OpenDHT còn bả ảệ o đ m s công b ng trong chia sẻự ằ lưu tr ữgiữa các client trong hệ thống OpenDHT đang được tri n khai trên PlanetLab, và ểngười dùng hoàn toàn có thể tương tác với nó thông qua RPC

Nhiệ m v c a luận văn ụ ủ

Thứ ấ nh t, tìm hiểu và khảo sát các khái niệm liên quan, c u trúc m ng và các thuấ ạ ật toán trong bảng băm phân tán Tìm hiểu mộ ố ệ ốt s h th ng bảng băm phân tán đã được phát tri n và tri n khai trên th c tể ể ự ế Qua đó đánh giá, nh n xét các ưu và như c điậ ợ ểm

của của kiến trúc bảng băm phân tán

Thứ hai, tìm hi u về ấể c u trúc mạng, cơ chế ạ ộho t đ ng của OpenDHT (giải pháp mở ủ c a

bảng băm phân tán) Tìm hiểu sâu các khía cạnh kỹ thuật của hệ thống Đánh giá khảnăng ứng d ng so v i h th ng bảụ ớ ệ ố ng băm phân tán truyền th ng K t h p tìm hi u một ố ế ợ ể

h ệthống cụ thể

Thứ ba, v n dụng các ki n thậ ế ức đã tìm hiểu ở trên Cài đ t mộ ứặ t ng dụng minh họa dựa trên ki n trúc mế ở ủ c a bảng băm phân tán

N ộ i dung luận văn

Sau đây là kết qu th c hi n lu n văn Lu n văn được trình bày theo các phân sau: ả ự ệ ậ ậ

• Phần 1: M ng ngang hàng và các hạ ệ ố th ng DHT Ở đây trình bày m t cách tổng ộquát nh t vấ ề ạ m ng ngang hàng bao gồm khái ni m chung, quá trình phát triệ ển, các ki n trúc và ế ứng dung tiêu biểu Sau đó đi sâu vào một ki n trúc c a mế ủ ạng ngang hàng đó là DHT, tìm hiểu kiến trúc và cơ chế làm vi c chung của DHT, ệcác loại ứng dụng, ưu và như c điểợ m Tìm hiểu các mạng DHT tiêu biểu đang đượ ử ục s d ng trên th c t ự ế

• Phần 2: Tìm hi u v Bamboo và OpenDHT Trong phể ề ần này ta đi sâu vào một DHT mà ta sử ụ d ng trong luận văn là Bamboo Sau đó ta tìm hiểu về OpenDHT đây là nội dung chính c a luận văn, ta sẽ đi sâu vào các vấ ề ủủ n đ c a một mạng OpenDHT là sự chia s (v hi u năng và v b nh ) c a các node trong mẻ ề ệ ề ộ ớ ủ ạng

Ta cũng đánh giá khả năng ho t đ ng c a chúng qua các th c nghiệm ạ ộ ủ ự

• Phần 3: Xây d ng m t ng d ng d a trên OpenDHT ng d ng mà ta xây d ng ự ộ ứ ụ ự Ứ ụ ự

ở đây là ng d ng multicast Trong đó trình bày vi c thi t k xây d ng m t ng ứ ụ ệ ế ế ự ộ ứ

dụng OpenDHT Mục đích là đánh giá khả năng tri n khai thực tế ộể m t ứng dụng OpenDHT, tìm hiểu xâu hơn các APIs để ử s dung khi xây dựng một ứng dụng OpenDHT Xây d ng thuự ật toán Multicast trên OpenDHT đểphát tri n các ể ứng dung khác hoàn thiện hơn và có chiều sâu hơn.

L ờ i cảm ơn

Trước tiên, tôi xin bày tỏ lòng c m ơn đếả n th y giáo hư ng d n TS Nguy n Khánh ầ ớ ẫ ễVăn Thầy đã hướng tôi đến một đề tài mà tôi c m th y r t thích thú và hữu ích cho tôi ả ấ ấtrong công việc sau này Đặc bi t là nhưng ch d n khoa h c và s t n tâm hư ng d n ệ ỉ ẫ ọ ự ậ ớ ẫgiúp đỡ tôi hoàn thành luận văn

Xin chân thành cảm ơn các thầy cô trong viện CNTT trư ng ĐHBK Hà N i, Viện đào ờ ộ

tạo sau đại học trư ng ĐHBK Hà N i, trư ng Đờ ộ ờ HBK Hà Nội nơi tôi đã được học tập suốt những năm đạ ọi h c và cao h c ọ

Cuối cùng tôi xin gửi l i cờ ảm ơn đến b n bè, ngư i thân và các b n (các anh ch ) cùng ạ ờ ạ ịlớp CNTT K79 Những ngư i đã luôn bên c nh giúp đ , đờ ạ ỡ ộng viên tôi trong suốt ch ng ặđường v a qua và những chặừ ng đường sắp tới

Danh m c thu t ng ụ ậ ữ

Peer to- -peer Mạng ngang hàng

Node Một thiết bị ối mạng (một peer) n

item Một đơn v ữị d u liệ

Structured Có cấu trúc

Overlay Mạng được xây dựng trên các mạng khác

Hash table Bảng băm

Distributed hash table Bảng băm phân tán

Join Gia nhập (mạng ngang hàng)

Leave Rời khỏi (mạng ngang hàng)

Churn rate S ố lượng peer rời khỏi/gia nhập mạng trong một kho ng ả

thời gian

put Lưu trữ ữ d liệu vào b ng băm ả

get Truy cập dữ ệu từ ảli b ng băm

Mạng P2P không có khái niệm máy trạm (client) hay máy chủ (server), mà chỉ có khái niệm các nodes(peers) đóng vai trò nh ả ư c client và server.

Hình 1.1 Mô hình client/server và mô hình P2P

1.1.1 Overlay network

Là mạng máy tính đư c xây dựợ ng trên nền của m t m ng khác Các nodes trong mộ ạ ạng overlay được xem là n i v i nhau bằố ớ ng liên k t ảế o (logical links), m i liên k t ảỗ ế o có th ểbao gồm rất nhiều các liên kết vật lí của m ng n n R t nhi u các m ng P2P đư c g i ạ ề ấ ề ạ ợ ọ

là overlay networks vì nó được xây dựng và hoạ ột đ ng trên nền của Internet VD: Gnutella, Freenet, DHTs ….Dial up Internet- cũng là một overlay network trên nền telephone network

Khái niệm overlay Networks trong DHT nói lên phương thức k t n i gi a các nodes ế ố ữtrong mạng, vìcác nodes được kết nố ới nhau qua mi v ột mạng hiện có, chẳng hạn như Internet, khái niêm overlay networks sử ụ d ng đ cung cể ấp chức năng định tuyến Hiện

có mạng lư i sau đó sớ ẽ ọ g ắi t t là underlay-networks ế N u underlay networks là Internet, thì việc định tuyến dựa vào sự trao đ i gi a các nodes trong DHT, và mổ ữ ỗi tuyến đi qua

-đó trong các tuyến được l a ch n trong underlay Overlay Networks cũng đư c s ự ọ ợ ử

dụng trong nhưng bối cảnh khác, chẳng hạn như để xây dựng mạng riêng ảo (VPN) Thuật ngữ ấ c u trúc overlay Networks đượ ử ục s d ng để phân bi t v i các mệ ớ ạng Overlay được t o ra b i DHTs t các Overlay Networks Hình minh h a 1.9 một Overlay ạ ở ừ ọNetworks và tương ứng của nó underlay Networks

Gần đây đã người ta ố ắ c g ng đểxây dựng overlays mà sử ụng một underlay mà cung d

cấp nhiều dịch vụ hơn so với mạng Internet ROFL thay thế các định tuyến dịch vụ ủa cInternet với một DHT, trong khi VRR có m t cách tiộ ếp cận tương tự cho mạng không dây

Peer to- -Peer là thu t nậ g ữ tương đối mới trong lĩnh vực m ng và các hạ ệ ống pth hântán Theo Oram, P2P computing bắ ầt đ u tr thành đ tài đưở ề ợc nhiều người quan tâm t giữa ừnhững năm 2000 Trong khoảng thời gian từ đó đ n nay, P2P trảế i qua vài th h , m i ế ệ ỗthế ệ ợ h đư c phát triển với nh ng đ ng cơ, m c đích cữ ộ ụ ủa mình

Hình 1.2 Mô hình centralized directory

Đóng góp chính của th h th nh t là đã ế ệ ứ ấ đưa ra kiến trúc m ng không xem các máy ạ

với vai trò tương đương nhau Mô hình centralized directory cho phép tìm kiếm thông tin trong không gian lưu trữ ộ m t cách nhanh chóng, tuy nhiên, điểm yếu của của mô

hình này là tính khả mở vì tải trên index server sẽ tăng tuyến tính với số lượng peer

Đồng th i các h th ng s d ng mô hình này, đi n hình là Napster còn gặp vấn v ờ ệ ố ử ụ ể đề ề

bản quyền các tài nguyên

Thế hệ thứ hai

Thế ệ ứ h th hai b t đ u với các ứng dụắ ầ ng như Gnutella, Freenet làm việc mô hình flooded requests Mô hình này không có bất kỳ server nào, các peer bình đẳng như nhau Các hệ thống peer to peer thế ệ ứ h th hai là các hệ ống peer to peer thuần túy thKhông gi ng thố ế ệ ứ h th nhất, các peer không thông báo về các nội dung chúng chia sẻ, khi một peer muốn tìm kiếm một file, nó gửi yêu cầu tới các peer kết nối trực tiế ớp v i

nó, nếu các peer đó không tìm thấy file, mỗi peer sẽ gửi yêu cầu tìm kiếm đến các peer kết nối trực tiếp với nó, quá trình cứ diễn ra như v y cho đậ ến khi request bị timeout Quá trình gửi yêu cầu tìm kiếm đi như vậy gọi là flooding Hình 1.3 biểu diễn một mô hình flooding request

Hình 1.3 Mô hình flooding request

Thế ệ ứ h th hai xóa b được m t sỏ ộ ố điểm xử lý tập trung trong mạng nhưng tính khả mở còn kém hơn do mạng sử ụ d ng thuật toán flooding sinh ra quá nhiều traffic

Thêm nữa, các mạng làm việc theo mô hình này không đảm b o sẽ tìm ợ ữ ệả đư c d li u có trên mạng do phạm vi tìm kiếm bị giới hạn Một số mạng trong thế h ệthứ hai đưa ra

một số ải tiế c n Freenet đưa ra mô hình document routing, trong đó d liệữ u đư c lưu ợtrên trên node có id tương tự ớ v i id của dữ liệu và các query được chuyển tiế ựp d a trên

id c a dủ ữ liệu tìm kiếm Kazza, Gnutella sử dụng khái niệm sup peer trong đó mộ ố er t snode hoạ ột đ ng như directory service, gi m lưả ợng flooding trong mạng

cộng đồng nghiên cứu là xây dựng một mạng P2P overlay khả ở không có điể m m điều khiển tập trung Nỗ ự l c giải quyết bài toán này là sự xuất hiện của “structured P2P overlay networks”

Thế ệ ứ h th ba được khở ầi đ u với các dự án nghiên cứu như Chord, CAN, Pastry, Tapestry và P Grid Các d- ự án này đưa ra khái ni m Distributed Hash Table (DHT) ệ

Mỗi peer trong hệ thống có một ID thu được từ việc băm các đặc thuộ tính đặ trưng c c

của peer đó như địa chỉ IP hay public key Mỗi data item cũng có một ID thu được theo cách tương tự ớ v i các peer Hash table lưu data dưới dạng c p key value Như vậy, ặ

node ID và cặp key-value được băm vào cùng một không gian ID Các node sau đó

đư c nối với nhau theo một topologyợ nào đó Quá trình tìm kiếm dữ liệu trở thành quá trình định tuyến với kích thước bảng định tuyến nhỏ và chi u dài đưề ờng đi cực đại Thế

h ệthứ ba đảm bảo xác xuất tìm thấy thông tin cao

Các DHT được xây d ng nh m m c đích cho phép các peer ho t đ ng như m t c u ự ằ ụ ạ ộ ộ ấtrúc dữ liệu phân tán với hai hàm chính Put(key,value) và Get(Key) Hàm Put lưu d ữliệu tại một peer nào đó sao cho bất kỳ peer nào cũng có th tìm đưể ợc bằng hàm Get Các hàm này hoàn thành sau khi đi qua mộ ốt s nh các ch ng Gi i pháp DHT đảỏ ặ ả m b o ảcho mạng có tính khả ở m và khả năng tìm thấy thông tin cao trong khi vẫn hoàn toàn phân tán DHT đang được xem như là cách tiếp cận hợp lý cho vấ ề địn đ nh vị và nh địtuyến trong các hệ ống P2P Cth ộng đồng nghiên cứu đã đưa ra nhiều DHT khác nhau Mỗi DHT hoạ ột đ ng theo nguyên lý chung và có ưu điểm riêng, Chord với thiế ết k đơn giản, Tapestry và Pastry gi i quyếả t được v n đ proximity routing … ấ ề

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 ở ức ứng dụng Các ứng dụng này rấ m 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

để thi t l p m ng P2P ế ậ ạ

2 Mạng chia sẻ file P2P:

Là mạng P2P phổ biến và nổi tiếng nhất trên Internet hiện nay Chức năngchủ yếu của mạng là cho phép tìm kiếm và truyền dữ liệu dựa trên giao thức IP (Internet Protocol).

Để truy c p vào m ng P2P này, ngườậ ạ i dùng ch c n download và cài đ t ph n mềm ỉ ầ ặ ầ

ứng dụng phù hợp cho máy tính của mình Có nhiều mạng P2P và phần mềm ứng dụng P2P tồn tại hiện nay Một số phần mềm chỉ s dử ụng được cho 1 mạng P2P nhấ ịt đ nh,

một số hoạ ột đ ng được với nhiều mạng P2P khác nhau Một số mạng P2P nổi tiếng trên Internet gồm: eDonkey, BitTorent, Gnutella

3 Phần mềm ứng dụng P2P

Các phần mềm ứng dụng P2P cầ ạn đ t đư c 7 tiêu chí căn bợ ản sau:

1 Giao diện người dùng không nằm trong trình duyệt (web browser)

2 Các máy tính trong hệ thống có thể đóng vai trò như cả máy tr m và máy chạ ủ

3 Phần mềm dễ ử ụ s d ng và đư c tích hợp nhiềợ u tính năng tốt

4 Ứng d ng hụ ỗ ợtr ngư i dùng tạo nội dung và thêm chức năng ờ

5 Ứng dụng cho phép tạ ế ố ếo k t n i đ n ngư i dùng khác ờ

6 Ứng dụng có nét “mới” và “thú vị”

7 Phần mềm ứng dụng hỗ trợ đa giao thức trên mạng

Một số phần mềm ứng dụng P2P nổi tiếng hiện nay bao gồm: Kazza, eMule, Bittorent, Limewire …

Giới thiệu Kazaa:

-Download: www.kazaa.com

-S dử ụng P2P technology (người dùng có thể ết nối trực tiếp vớ k i người dùng khác)

-Kazaa cho phép: Tìm và download các files đã được chia sẻ ởi những nhà cung cấp bchuyên nghiệp và người dùng

-Kazza có sử dụng những kết nối nhanh với các SuperNodes: Mỗi SuperNode chứa danh sách các files chia sẻ ở b i ngư i dùng và nơi lưu tr file ờ ữ

Giới thiệu Emule:

-Download: www.emule.com

-Một trong những phần mềm chia sẻ file P2P lớn nhất giữa các Clients trên Internet

-Verson mới nhất: eMule 0.49b

-Có thể ử ụ s d ng eMule đểchia sẻ và download tấ ảt c các lo i files trên Internet ạ

Giới thiệu Skype:

-Download: www.skype.com

-Là phần mềm P2P VoIP phát triển bởi những ngư i đờ ã làm Kazaa

-Skype cho phép người dùng đàm thoại và g i message tử ới người dùng Skype khác -Đây là một overlay network, có 2 loại nodes: Original Host (OH) và Super nodes (SN)

+ OH là một phần mềm ứng dụng cho phép sử ụ d ng đ đàm tho i và gể ạ ửi message.+ Những node có địa chỉ IP tĩnh, CPU, memory, băng thông đủ ạ m nh thì có thể được xem xét chọn làm super node

Hình 1.4 Mô hình skype

+ OH kế ố ớ ột n i v i m t SN và phải đăng kí v i Skype login server đớ ể login thành công

1.2 Tìm hi u DHT ể - B ảng băm phân tán

1.2.1 DHT là gì?

Một bảng băm phân tán là gì? như tên của nó cho thấy, nó là một bảng băm được phân tán giữa các máy tính kết n i vố ới nhau, các máy tính đó được g i là các nodes Giọ ống như mộ ảt b ng băm, nó có chứ ặa c p key/values, ta sẽ ọ g i chúng là các b n ghi Ch c ả ứnăng chính của d ch v ợc cung cấ ởị ụ đư p b i m t DHT là lookup operation, nó trả ềộ v

value của một keytương ứng Trong kịch bản sử ụ d ng điển hình, một client đưa ra một

key mà nó mong mu n lố ấy được những values tương ng Qua đó, ứ client cung cấp keys

tại bất kỳ ột trong các nodes, sau đó sẽ thực hiện việc lookup operation m và trả ại l

những values có keys tương ứng Ngoài ra, một DHT còn có các thao tác khác để ảqu n

lý các bản ghi, ví dụ như insert và delete bản ghi

Các đại diệ ủn c a các cặp giá trị key/value có thể được tùy biến Ví dụ, key có thể là m t ộchuỗi ký tự hay m t đ i tưộ ố ợng Tương tự như vậy, values có thể là một chuỗi ký tự,

một số, hoặc một số nhị phân đại diện của mộ ố ợ t đ i tư ng bất kỳ Các đại diện trên thực

t s ế ẽphụ thuộc vào các ứng dụng cụ thể

Mộ ềt đi u quan trọng trong tính chất c a DHTs là hiủ ệu quả ử x vlý i s lư ng lớ ản ớ ố ợ n bghi Hơn nữa, s lư ng các nodes có th r t l n, t m t vài nodes đ n nhiềố ợ ể ấ ớ ừ ộ ế u ngàn ho c ặhàng triệu nodes Vì không giới hạn lưu trữ ộ/b nh và kh năng chi phí c a insert và ớ ả ủupdate các bản ghi, việc định vị lưu tr ữ các bản ghi trong mỗi node là r t mấ ềm dẻo Vì vậy, mỗi node có trách nhiệm lưu trữ ộ m t số ợ lư ng bản ghi nhấ ịt đ nh, đó g i là lưu trọ ữ

cục bộ

Như đã nói ở trên, m i node sẽỗ có th lookup các values ể tương ứng v i m t key ớ ộ nào đó

Vì t t c các bấ ả ản ghi không đư c lưu trợ ữ ạ t ấ ả i t t c các node, nên ta ph i có m t thao tác ả ộ

định tuy n t i m t node có th lưu tr các b n ghi đư c yêu c u Đ i v i m c đích này, ế ớ ộ ể ữ ả ợ ầ ố ớ ụmỗi node có một bảng định tuyến có chứa đư ng đi đờ ến nodes khác, gọi là các node’s neighbors Vì v y, m t truy vậ ộ ấn được chuy n thông qua các neighbors như vậể y và cu i ốcùng nó đạ ớt t i node có khả năng cung cấp cho các key Hình 1.7 Minh h a m t DHT ọ ộ

là sự ánh x các URL hiệạ n thờ ại đ i diện cho vị trí c a file.ủ

Để 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 thỏa mãn nhất (Theo một tiêu trí nào đó) 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 thỏa mãn nhất 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

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.8 Kiến trúc của một ứng dụng trên DHT

Các DHTs đầu tiên xuất hiện vào năm 2001, và xây d ng trên mộự t trong hai ý tưởng đưa ra vào năm 1997[10]:

• Consistent hashing, đó là mộ ất c u trúc hasing trong caching web trong nhiều nodes, theo đó số lư ng củợ a cache items c n bịầ xáo tr n là nh nhất khi các ộ ỏnodes được thêm vào ho c g b ặ ỡ ỏ

• PRR2 hoặc Plaxton Mesh, là m t c u trúc cho phép client đ nh tuy n cho các ộ ấ ị ếnode có cho các mộ ố ợt đ i tư ng, nó yêu cầu m t b ng đ nh tuy n nh ộ ả ị ế ỏ

-networks được xây d ng Thông điệp nộ ộự i b giữa các nodes trong overlay-networks di chuyển theo các vòng Topology của overlay-networks, nhưng thực ch t thông qua các ấliên kết và định tuyến cho rằng hình thức underlay mạng

Trong các hệ thống DHTs đầu tiên, Chord [11] được xây dựng trên Consistent hashing, nhưng thay thế các thông tin chung c a toàn b m ng b ng mộ ảủ ộ ạ ằ t b ng đ nh tuyến tại ị

mỗi node Chord đã được tái sử ụng các thiết kế ủa các hệ thống DHTs khác như d cKoorde, EpiChord, Chord #, và Distributed k ary (DKS)- [10]

Tương t như vự ậy, PRR là n n tảề ng c a DHTs Tapestry và Pastry M t s h th ng m ủ ộ ố ệ ố ở

rộng PRR sao cho hệ thống hoạ ột đ ng trong khi các nodes được joining, leaving, và failing

Content-Addressable Networks (CAN) và P-Grid không trự ếp xây dựng dực ti a trên các ý tư ng đó, mở ặc dù nó m t s điểộ ố m tương đ ng v i PRR.[10] ồ ớ

Tính năng phân biệ ủt c a DHTs(Distinguishing Features of DHTs) Như trên đã trình bày, các mô tả ủ c a một DHT tương tự như h th ng tên mi n (DNS), cho phép khách ệ ố ềhàng để truy v n bấ ỳấ t k máy ch DNS cho các đ a ch ủ ị ỉIP được liên k t v i m t tên máy ế ớ ộchủ DHTs cũng có thể được sử ụ d ng đ cung c p một dịể ấ ch vụ như v y Đã có những ậ

đề xu t như v y, và nó đã đư c đánh giá b ng th c nghiệm Các thửấ ậ ợ ằ ự nghi m ban đ u ệ ầcho thấy hoạ ột đ ng kém hiệu quả ặc dù nh ng l, m ữ ỗ ự l c gần đây đã cải thiện ph n nào ầhiệu quả ủ c a các hệ thống DNS Tuy nhiên, DHTs có nh ng thuữ ộc tính khác khi n nó ếphân biệt khỏi hệ thống DNS

Thuộc tính phân biệt gi a DHT và DNS là tữ ổ chứ ữ liệ ủa nó là tự quản lý Cấc d u c u trúc bên trong để config b ng tay của các hệ thốằ ng DNS là r t nhiềấ u và ph c tạp Kiến ứtrúc bên trong c a DNS là mủ ột cấu trúc hình cây, trong đó được chia thành các khutương ứng với các nhánh c a cây Các máy ch trong m i khu v c ph i ch u trách ủ ủ ỗ ự ả ịnhiệm cho một khu vực c a không gian tên Ví d , các máy ch trong mủ ụ ủ ột vùng cụ ể th

có thể chịu trách nhiệm đối v i t t c các tên miớ ấ ả ền kết thúc bằng Com Các máy chủchịu trách nhiệm về ữ nh ng tên và cả ánh x n đạ đế ịa ch IP cỉ ủa nó, hoặc các tách ra các vùng nhỏ hơn m i vùng nhỗ ỏ là môt máy ch Ví dụ, ủ trong khu vực máy chủ Com trên

có th tách ra các máy chể ủ nh hơn ch chịỏ ỉ u trách nhiệm ánh xạ các tên có k t thúc ếabcd.com Toàn bộ ấ c u trúc của cây này được xây dựng bằng t ay

DHTs ngược lại với DNS, tự động quyế ịt đnh mà node trả ại các bản ghi Nếu nodes lhiện đang lưu trữ ộ m t số ả b n ghi đã được gỡ ỏ b khỏi hệ thống DHT tự ả qu n lý bằng cách sao chép các bản ghi đó sang các nodes khác Vì vậy, nodes có thể tiếp tục tham gia và r i kh i hờ ỏ ệ thống Các DHT sẽ đả m bảo rằng các bảng định tuyến luôn được cập

nhật, và các bản ghi được phân phối, chẳng hạn rằng các hoạ ột đ ng cơ bản v n làm ẫviệc Điều này join hoặc leave các nodes được g i t t là churn hoọ ắ ặc network dynamism

Một tính năng chủ chốt của DHTs là khả năng chịu lỗi Điều này ngụ ý rằng lookups

vẫn có thể thực hiện được ngay cả khi có một số nodes bị ỗ Vì vậy lỗi có thể được bỏ l iqua đến mộ ứ ột m c đ nào đó mi n là có m t s tr l i c a các b n ghi trên m t s nodes ễ ộ ố ả ờ ủ ả ộ ốcòn sống

Dưới đây là mộ ố ểt s đi m m nh c a DHTs đư c các nghiên c u trư c đây đ c p đ n ạ ủ ợ ứ ớ ề ậ ế

Một chủ đề nghiên cứu trung tâm của các hệ thố ng DHTs đ u tiên đã đư c đưa ra là ầ ợlàm thế nào đ gi m số ầể ả l n re routes- , thường gọ ắi t t là hops, của bất cứ yêu cầu tìm

kiếm sẽ có được trư c khi đớ ến với responsible node (node đáp ng) Có hai lý do Đứ ầu tiên, số hop t l thuận vớ ố ầỉ ệ i s l n truyền thông đi p như vệ ậy sẽ ố t n thời gian và hiệu năng Do đó, giảm b t s hops thườớ ố ng làm gi m th i gian đ thựả ờ ể c hi n m t lookup ệ ộ

Thứ hai, càng có nhi u hops, các xác su t gề ấ ặp ải các nodes bị ỗph l i là cao hơn trong khi th c hiự ện lookup

Nhiều nghiên cứu cũng đã được tiến hành về cách gi m kích cả ỡ ủ c a bảng định tuyến

(routing tables) Nguyên nhân chính là các thành phần trong bảng định tuyến (routing tables) luôn được cập nhật các nodes luôn luôn join và leave khỏi hệ thống Điều này được g i t t là Topology maintenance Thông thườọ ắ ng, đi u này đưề ợc th c hiện bằng ựcách dò tìm s các nodes trong bự ảng định tuy n tế ại những thời gian để đả m bảo rằng các thông tin định tuyến đư c cập nh tợ ậ Tuy nhiên, phương pháp tiếp cận lazy

Topology maintenance cũng được s dử ụng, đó là nodes được thêm vào ho c g b ra ặ ỡ ỏ

bảng định tuyến khi việc tìm kiếm phát hiện ra một nodes mới (thêm vào bảng định tuyến) hoặc m t node b i (gộ ị ỗ l ỡ ỏ b ra kh i bỏ ảng định ến) Nói chung, nếu các bảng tuy

định tuy n l n, thì t n nhi u băng thông là cần thiế ểế ớ ố ề t đ duy trì nó

Có một ràng bu c gi a các sộ ữ ố ợ lư ng tối đa hops và kích cỡ ủ c a bảng định tuyến Nhìn chung, số ợ lư ng củ ảa b ng định tuyến càng l n thì s ớ ốhops càng nhỏ, và ngượ ạc l i

Một số DHTs [11 13,, 14] có thể đảm bảo việc tìm kiếm các các ản ghi ằng số lượng b bhops ít hơn hoặc b ng hàm logarithm c a s nodes Ví d , m t h th ng có ch a 1024 ằ ủ ố ụ ộ ệ ố ứnodes, thì số ợ lư ng tối đa các hops để nhả ới đích là logy t 2(1024) = 10 Đồng th i, m i ờ ỗnode cần phải lưu giữ ộ ả m t b ng định tuyến có kích thước là logarithmic s ốnodes

Trong nhiều hệ ố th ng hàm logarithm có thể được cấu hình như là một tham số ủ c a hệthống Trong tất cả các hệ thống dựa trên PRR, kích thước các bảng định tuyến là k*L, trong đó k được đặ ằt b ng cơ sở ừ tr đi 1, và L là logarithm c a kích thư c h th ng v i ủ ớ ệ ố ớ

cơ sở là k Ví d , nếụ u các cơ sở được đặt là 2, số ợlư ng t i đa hops trong m t node h ố ộ ệthống có 4096 node sẽ là log2 (4096) = 12, trong khi kích thước bảng định tuyến của nó

s ẽlà 1*log2(4096) = 12 Nế ặu đ t cơ sở là 16, các s lư ng tố ợ ối đa hops trong một node

4096 hệ ố th ng sẽ đư c logợ 16(4096) = 3, trong khi kích thước bảng định tuy n s đư c ế ẽ ợ15*log16 (4096) = 45

Ta cđề ập đ n hai trưế ờng h p thú vợ ị là nói đ cấu hình cơ bản Mộến t là để đặ t cơ s cho ởvuông gốc c a hủ ệ thống kích cỡ Như vậy, t t c các truy v n có thấ ả ấ ể được giải quyết trong tối đa hai hops Điều này có thể ợ đư c xem bởi sau công th c toán hứ ọc sau, khi n được đặt thành s lư ng các nodes trong h th ng: ố ợ ệ ố

Các cài đặ ởt trên c a bảủ ng định tuy n vuông g c và hai hop tra cứu là thiết lập trong ế ố

h ệthống như Kelips và Tulip Thứ hai, bảng routing table chứa toàn bộ ố nodes trong s

h ệ thống, trong đó có trường hợp tất cả các truy vấn có thể được giải quyết trong một hop, từ logn (n) = 1

Hiện nay, chúng ta đã đề ậ c p đến các hệ thống định tuyến trong đó có các bảng kích thư c tăng lên như là s lư ng các nodes tăng Tuy nhiên, chớ ố ợ ẳng hạn như các hệ thống

CAN cố đị nh kích thư c c a bớ ủ ảng định tuyến Các số ợ lư ng tối đa hops sau đó s đưẽ ợc theo thứ ự ủ t c a hình vuông gố ủ ố c c a s nodes.

Một câu hỏ ặi đ t ra là số lượng routing table là bao nhiêu đểcó thể để giảm số lượng tối

đa hops Mộ ết k t qu đư c bi t t lý thuyả ợ ế ừ ết đồ thị ọ, g i là b ràng bu c Moore tị ộ ối ưu cho

s ố lượng tối đa hops một hệ thống n nodes có thể đảm bảo nếu mỗi node có log(n) con trỏ đế n các nodes khác Những trạng thái với n nodes, khi m i node có log(n) giá trỗ ị

định tuy n, s lư ng t i đa hops đư c cung c p b i b t k h th ng có th không đư c ế ố ợ ố ợ ấ ở ấ ỳ ệ ố ể ợtiệm cận với giá trị Error! Bookmark not defined.A A

))log(log(log(n)n M t sộ ố ệ h thống,

chẳng hạn như Koorde và Distance Halving, có thể ực sự đảth m bảo tối đa số hops là

))

log(log(log(n)n với log(n) con trỏ định tuyế [1] Trong khi vin ệc thiết kế các hệ thống này

đã được ch ra, mỉ ột phương pháp tiếp cận đơn gi n đã đưả ợc đề ngh t đư c cùng ị để đạ ợmột kết quả Nếu mỗi node, thêm hi u biể ết thêm mình có m t bộ ảng định tuyến hàng

xóm (neighbors’ routing table), thì số ợ lư ng các hops sẽ được tối ưu thêm so với các

h ệthống cũ DHTs Lưu ý rằng Topology maintanance nhằm tránh việc thêm giá trị vào các bảng định tuyến

S ố lượng các hops không chỉ xác đ nh thờị i gian để ế ti p cận với các đi m đ n, để ế ộ ễ tr

của mạng (network latencies) và tố ộc đ của các node cũng tương đối quan trọng Một minh họa đơn giản là m t k ch bộ ị ản hai hop hệ ố th ng thông điệp từ ộ m t tuyến đường

đến Nh t B n và Châu Âu quay lậ ả ại sẽ ớ l n hơn rất nhiều là các hop trên cùng một khu

v cự Đối với ví dụ khác, hãy cân nhắc việ ịc đ nh tuyến từ các node vào node d đến e trên Overlay của mô tả Hình 1.9 Mất hai hops trên overlay network thông qua để ợ vư t qua con đường d-a-e Nhưng trên underlay nó ph i đi qua 5 hops hops thông qua con ảđường d-f-g-e-a- e

Một thư c đo đướ ợc gọi là stretch thường được sử ụ d ng để nhấn mạnh những chi phí thời gian trễ ủ c a DHTs Stretch của vi c tìmệ đường là thời gian dành cho DHT để đị nh tuyến thông qua các tuyến đư ng đó, là chi phí thờờ i gian từ node ngu n đ n đích đ ồ ế ểgiao tiếp M t ví dộ ụ minh họa, nếu một trong các lookup DHT đi các máy x1, x2 xn,

và d (xi, xj) là thời gian để ử g i một thông điệp từ ớxi t i xj, Như vậy công thứ ểc đ tính

stretch là d(x ,1x2)+d( x1+,xn d()xn− ,1xn)

stretch của toàn bộ ệ h ống là stretch lớn nhất thcho bất kỳ tuyến đường nào Trong thực tế, chúng ta đã so sánh thời gian cho các DHT

để đị nh tuy n m t thông đi p thông qua nodes khác nhau, với thời gian nguồn và đích ế ộ ệ

đã truyền đạt trực tiếp mà không có sự tham gia c a DHT Thông báo rằng trong thực ủ

tế, nguồn và đích không thường lấy thông tin của nhau (thường ch có m t chi u), t ỉ ộ ề ừ

mỗi node chỉ biết một phần nhỏ ủa các nodes khác c

Một số DHTs, chẳng hạn như những DHT ự d a trên PRR, được cấu trúc như vậy có thể

có m t sộ ố ề m m dẻo trong lựa chọn giữa các nodes trong b ng đ nh tuy n [13,14] Do ả ị ếvậy, mỗi node có cố ắ g ng chọn những nodes trong các bảng định tuyế có độ trễ nhỏ n Điều này thư ng đườ ợc g i là s l a ch n các nodes hàng xóm g n (ọ ự ự ọ ầ proximity neighborn Selection PNS) Các hệ thống khác không có sự ề m m dẻo này, nhưng thay vào đó vì tăng kích thước c a bủ ảng định tuyến để có nhiều nodes để ự l a chọn khi định tuyến Kỹ thuật này được g i t t là l a chọ ắ ự ọn tuyến đường gần (proximity route selection PRS) Thử nghi m đã chỉệ ra r ng PNS cho stretch ằ thấp hơn PRS

Vì số ợ lư ng các nodes tăng, nó s trở thành thách thẽ ức không nhỏ cho mỗi node trong việc tìm ki m các nodes có trế ễ thấp nhất Lý do là các node cần thăm dò nhiều nodes trước khi tìm ra những node g n nh t Hoạ ộng trên mạầ ấ t đ ng h n t p cho thấy cách thức ỗ ạnày có thể được th c hiự ện một cách mềm dẻo Ví d , trong Vivaldi ụ , mỗi node tập hợp những thông tin trễ ừ ộ t m t số máy khác và sau đó mỗi node sẽ nh n đư c một vị trí ậ ợphối hợp trong một không gian hợp lý Ví dụ đơn gi n, không gian 3-chiều, mỗi node ả

s ẽ nhận được một tổng hợp (x, y, z) phối hợp Các tọ ộa đ tính được khoảng cách

Euclidean giữa hai nodes t ng hợổ p các ước tính m ng lư i t a đ trễ giữạ ớ ọ ộ a hai nodes S ựphát triển ở chỗ ộ m t node không cần phả ự ếp giao tiếp với tr c ti i các node khác để biết

mức độ trễ khi tương tác với nó, nhưng có th ướể c tính các trễ ổng hợp từ các tọ ộ t a đ

của các node, mà nó có thể nhận được từ nodes khác hoặc từ ột dịch vụ m

1.2.4 Các thuộc tính quan trọng của DHTs

Chúng ta ng h tổ ợp và tóm tắt các thu c tính quan trộ ọng nhất mà định tuyến được mở

rộng Việ ịc đnh tuyến có thể được mở ộng Số lượ g các hops luôn nhỏ r n hơn ho c ặbằng log(n) và mỗi node cũng chỉ ch a s lư ng các con trỏ ứ ố ợ node nhỏ hơn ho c bằng ặlog(n), trong môt hệ thống có n nodes

Các con trỏ nodes phân tán đều Mỗi node lưu trữ trung bình d/n b n ghi, trong đó d là ả

s ố lượng các bản ghi trong DHT, và n là số nodes

Quy mô của hệ thống có tính động Mỗi thao tác join/leave c a mủ ột node trung bình đòi hỏi ph i phân phố ạả i l i d/n b n ghi, trong d là s lư ng các b n ghi trong DHT, và n ả ố ợ ả

là số nodes

DHTs tự quản lý các b n ghi và thông tin đ nh tuyến khi: ả ị

Nodes join, thông tin định tuyến được c p nh t vào các nodes t o mớậ ậ ạ i, và các b n ghi ảtrong routing table được phân ph i l i ố ạ

Nodes leave, thông tin định tuy n đư c cậế ợ p nh t lại, và các bản ghi trong routing table ậđược phân phố ại l i trư c khi node đó rờớ i kh i h th ng ỏ ệ ố

Nodes fail Các nodes fail đư c tìm ra và thông tin đợ ịnh tuy n đư c cậế ợ p nhật để ghi nhận chúng Routing table s t ng khôi phục ẽ ự độ

Ngoài vi c trên, mệ ột số ệ h thống tự quản lý tải trên các nodes, trong khi những hệ thống khác tự ả qu n lý để khôi ph c l i tụ ạ ừ các mối đe dọa an ninh

Hình 1.10: Một tấn công Sybil Node c đại diện cho các nodes c, d, và e trong overlay

network

1.2.5 Bảo mật và xác thực

Bảo mật cần phải được xem xét cho tất cả các hệ thống phân tán, và DHTs không phải

là ngo i lạ ệ M t trong nhộ ững loại hình cụ thể ủ c a cu c tộ ấn công đó đã được nghiên cứu

là Sybil attack[15] Các cu c tộ ấn công này là một host độc hại đã join tham gia các DHT với nhi u nhề ận dạng (xem hình 1.10) Do vậy, bất kỳ ỹ k thuật mà dựa vào một số yêu cầu chính xác để phát hiện các k t quế ả độ c hại ho c phát hiặ ện hành vi ứng xử ở tr nên không có hi u quệ ả Để chống lại sự ấ t n công này là sử ụ d ng một số phương ti n đ ệ ểthiết lập sự ậ nh n dạng của các nodes

Một cách để nhận dạng của các nodes của DHT là sử ụng khóa công khai trong mã dhóa Mỗi node trong DHT được xác minh đ có mể ột chứng nhận hợp lệ ạ t o ra bởi trusted certificate authority Do đó, các nodes trong DHT có thể ợ đư c coi là đáng tin

cậy Sự giả đị nh này có ý nghĩa trung tâm của hệ thống, chẳng ạn như Grid hoặ ệh c h thống file system Tuy nhiên, điều này không khả thi đ i v i mố ớ ột hệ thống mở, chẳng

hạn như là một hệ thống thoại Internet như Skype

Tạo ra nhận dạng node dạng bằng cách sử ụng chứng nhậ d n là không đ để đảủ m bảo an ninh Thậm chí những nodes tin cậy chính là nhứng nodes độc h i hoạ ặc nh ng node kữ ẻthù Vì vậy, an ninh phải được xem xét ở ấ t t cả các cấp và các giao th c cứ ủa hệ thống

cần phải được thiết kế như vậy là khó đ ạể l m dụng hệ thống

Các vấ ề ền đ v an ninh xem xét cho DHTs bị ấ t n công khi định tuyến Ví dụ, một node

có thể đị nh tuyến sai node, hay sai hư ng đớ ịnh tuyến Hầ ếu h t các kỹ thu t đ ngăn ậ ểchặn các lo i tạ ấn công có liên quan đến việc xác minh không thay đổ ủi c a thu c tính h ộ ệthống, chẳng hạn như b o đả ảm rằng luôn luôn làm cho tiến trình định tuy n vế ề hư ng ớđiểm đ n Nodes đế ộc h i cũng có th t ch i s t n tạ ủ ữ ệạ ể ừ ố ự ồ i c a d li u Đi u này có thể ềngăn ngừa được b ng cách so sánh các k t qu t các b n sao khác nhau, v i đi u kiện ằ ế ả ừ ả ớ ề

là các bản sao không phải là t Sybil attackừ [15] Cuối cùng, DHT cũng có tấn công từ

chối dịch vụ, chẳng hạn như cho phép nhiều nodes join và leave hệ ống một cách ththường xuyên, như vậy hệ thống sẽ đổ ỡ v

Cuối cùng, không thể ừng lạ ừ d i t nodes có hành vi độc hại, đặc bi t là trong mệ ột quy

mô một overlay lớn và ở cho bất kỳ người dùng nào và không s m ử ụ d ng khóa công khai M t câu h i quan trộ ỏ ọng là làm sao để đị nh đư c nhữợ ng nodes là đáng tin cậy và

nh ng ữ nodes độc h i Mạ ột trong những giải pháp này là đoán nhận hành vi trong quá

khứ và l ch sử ủị c a node như là m t biộ ểu ệ ủhi n c a nó sẽ hành xử như thế nào trong tương lai Nghiên cứu v ề trust managerment ng cách thu thậ bằ p, x lý, và ph bi n ử ổ ếthông tin phản hồi về quá khứ ủ c a hành vi tham gia nodes

Như phần trên đã trình bày, thao tác chính c a DHT là lookup Tuy nhiên, m t s thao ủ ộ ốtác khác cũng thường xuyên được sử ụ d ng, chúng ta đề ậ c p đ n ế ởđây là: range queries

và group communication

Range queries, Trong m t sộ ố ứ ng dụng, có th có mể ột yêu cầ ặu đ t ra là mu n tìm mố ột

tập các values cho tất cả các keys, trong đó các keys lày là một loạ các số hoặc chữ cái t

trong bảng chữ cái alphabetical Ví dụ, trong môi trư ng tính toán lườ ới, các keys trong DHT có thể đại diện cho khả năng của CPU Theo đó, một ứng dụng có thể đưa ra yêu

c tầu ìm kiếm tất cả các giá trị ới các keys nằm trong khoảng 2000 – 5000 MHz vRange queries trong DHT lầ ần đ u tiên đư c đợ ề ậ c p bởi Andrzejak và Xu [12] Sau đó được phát tri n trên t t c các DHT b i các nghiên c u khác Thự ếể ấ ả ở ứ c t có m t s nodes ộ ốlưu trữ nhi u b n ghi hơn so v i các node khác, vì vậy các luồề ả ớ ng khi th c hi n range ự ệqueries là không cân b ng, các hằ ệ thống Mercury và SkipNet th c hi n các range ự ệqueries mà bỏ qua được vấn đề này V n đ này cũng là mấ ề ột vấn đề ầ c n nghiên cứu Group Communication Các thông tin tìm đường trong đó đã được lưu trong các hệthống DHTs có thể ợ đư c sử ụ d ng cho mục đích group communication Các thông tin tìm đường đó được sử ụ d ng c trong thao tác lookups và trong c group ả ảcommunication Routing tables trong DHT được sử ụ để d ng broadcast m t thông đi p ộ ệ

t mừ ột node đến tất các các nodes khác trong overlay network Ta có thể cài đặt các nodes có thể ậ nh n thông đi p trong một sệ ố bư c nhớ ấ ịt đ nh, hoặc mộ ốt s node có kh ảnăng forward thông điệ ớp t i m t vài nodes khác ộ

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ộ rời khỏi mạng do một số nguyên nhân t 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ử ụng DHT d

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

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 ại ất lđược chia đôi, … Hình 1.11 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 Hình 1.11(b) Node n chọn các finger của nó ng cách xem nó như là đibằ ể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 + 23 chia không gian ID thành hai phần bằng nhau, ID trư c đó n + ớ 23 chia nửa thứ nhất thành hai phần bằng nhau, ID n + 21 chia phần tư đầu tiên thành hai ph n b ng nhau, tương t ầ ằ ựID n +

20 chia 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àmfinger Hình 1.4(c) cho thấy bảng định tuyến của node 3 và node 11

Hình 1.11 (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

Mapping Items Onto Nodes

Như chúng ta thấy trên Hình 1.11, m t item đư c lưu trên node đ u tiên mà theo sau ộ ợ ầ

nó theo chiều kim đồng h trong không gian ID Các item v i ID tương ng 2, 3, 6, ồ ớ ứ10,13 được lưu trong các node trên mạng như sau: {2,3} được lưu tại node 3; {6} được lưu t i node 9; {10} đư c lưu t i node 11; và {13} đư c lưu tạ ợ ạ ợ ại node 0

Lookup Process

Quá trình tìm kiếm là kết quả tự nhiên của cách chia không gian ID Cả việc chèn và tìm kiếm dữ liệu đều d a trên việc tự ìm ID successor của một ID Ví dụ, khi node 11

muốn chèn một item m i vớ ới ID là 8, lookup được chuy n tiể ếp tới node 3 là node đứng trước gần node 8 nh t trong bảng finger của node 11 Node lại thực hiện quá trình ấ

tương tự, nó chuyển tiếp yêu cầu tới node 5 là node đ ng trưứ ớc gầ 8 nhất trong bảng n finger của nó Node 5 thấy rằng 8 nằm giữa nó và successor của nó (node 9), do đó nó trả ề ế v k t quả 9 theo đư ng đi ngườ ợc lại Sau khi nhận được câu trả lời, tầng ứng dụng trên node 11 sẽ liên lạc với tầng ứng dụng trên node 9 và yêu cầu lưu một số giá tr v i ị ớkey là 8 B t kấ ỳ node nào mu n tìm kiếm key 8 đều thực hiố ện quá trình tương tự và trong không quá M chặng, một node s ìm ra node lẽ t ưu các dữ liệ ứu ng với key 8 Nói chung, trong điều kiện thông thường, một tìm kiếm sẽ hoàn thành trong O(log2(N)) chặng

Joins, Leaves and Maintenance

Khi node n muốn join vào mạng, nó phải tìm ID của mình thông qua một số contact trong mạng và chèn bản thân nó vào vòng giữa successor s của nó và predecessor của s

sử dụng một thuật toán stabilization chạy định kỳ ả B ng đ nh tuy n cị ế ủa n được khở ại t o bằng cách copy bảng định tuyến của s hoặc yêu cầu s tìm các finger của n Tập các node cần điều chỉnh bảng định tuyến sau khi n join vào m ng nhạ ờ các node này đ u ềchạy thuật toán stabilization định kỳ Nhiệm vụ cuối cùng là chuyển một phần các item đang lưu trên node s có ID nhỏ hơn ho c b ng n sao nodeặ ằ n Việc di chuyể ữ ện d li u này được th c hi n bở ầự ệ i t ng ứng d ng c a n và s ụ ủ

Hình 1.12 cho chúng ta thấy một ví dụ về quá trình join vào mạng của một node

Giả ử s node 21 có successor là node 32, trên node 32 đang lưu các key 24 và 30 Node

26 join vào mạng, sau quá trình tìm kiếm, node 26 biết node 32 là successor của mình,

nó trỏ con trỏ successor của mình vào node 32 và báo cho node 32 biết Node 32 sau khi được báo thì trỏ con trỏ predecessor vào node 26 Node 26 copy các key tương ứng

với nó (key 24) từ node 32 Đế ịn đnh kỳ, N21 chạy quá trình stabilize, lúc này con trỏ successor vẫn trỏ vào node 32 Node 21 hỏi node 32 về predecessor của node 32, lúc này predecessor của 32 là 26 Sau khi nhận được câu tr l i, N21 tr con tr ả ờ ỏ ỏ successor

vào node 26 và báo cho node 26 biết nó là predecessor của node 26 Node 26 trỏ con trỏ predecessor vào node 21

Hình 1.12 Quá trình một node join vào mạng

Quá trình rời khỏi mạng có báo trược được th c hiệự n như sau: node sắ ờp r i khỏ ại m ng chuyển các key nó đang lưu sang successor c a nó rồi báo cho các node predecessor và ủsuccessor Bảng định tuyến của các node liên quan sẽ được cập nh t khi các node này ậchạy thuật toán stabilization

Hình 1.13 dưới đây cho chúng ta một ví dụ ề ả v b ng định tuyến của các node khi có sựjoin/leave Ban đầu m ng có 3 node vạ ới ID là 0, 1, 3, b ng đ nh tuy n c a chúng đư c ả ị ế ủ ợcho th y trên hấ ình vẽ.

Sau đó node 6 join vào mạng rồi node 3 rời kh i m ng, bỏ ạ ảng định tuyến của các node

và sự thây đ i bảổ ng định tuyến được thể ệ hi n trong hình vẽ với những phần thay đổi có màu đen, những phần không đổi có màu xám

Hình 1.13 (a) Bảng finger và vị trí của key sau khi node 6 join (b)Bảng finger và

vị trí của key sau khi node 3 leave.

Replication and Fault Tolerance

Các node rời khỏ ại m ng đột ngột có hai tác động tiêu c c Thự ứ nhất là dẫn đến mất dữliệu lưu trên các node này, thứ hai một phần của vòng bị mất liên k t dế ẫn đến mộ ố t s

ID sẽ không được tìm thấy Có thể xảy ra tình huống một dãy các node liền nhau cùng rời khỏi mạng đột ng t Chord giảộ i quy t vế ấn đề này bằng cách cho mỗi node lưu một danh sách log2(N) node theo sau nó trong không gian ID Danh sách này có hai mục đích, thứ nh t là nếấ u m t node phát hiện successor của nó không hoộ ạ ột đ ng, nó sẽ thay thế ằ b ng node ngay cạnh trong successor list, th ứ hai, mọ ữ liệi d u đư c lưu trên mộợ t

node nào đó cũng được lưu trên các node trong successor list Dữ liệu chỉ bị mất hay vòng chỉ bị đứt khi có log2(N) + 1 node liên tiếp fail đồng th i ờ

Upper Services and Applications

Một số ứng dụng như cooperative fil system [14], một ứng dụe- ng đọc/ghi hệ thống file

và một DNS đã được xây dựng dựa trên Chord Đồng thời, một thuật toán broadcast cũng được phát tri n cho Chord ể

Implementation

Cài đặt chính của Chord được thực hiệ ằn b ng nghôn ng C++ Thêm n a, một C++ ữ ữdiscrete-event simulator cũng đ được xây d ng Naanou là mã ự ột cài đặt C# của Chord với một ứng dụng chia sẻ file đư c xây d ng d a trên nó ợ ự ự

Overlay graph

Kademlia graph tổ chức các ID trong không gian vòng tròn trong đó ID của các node là

lá c a cây nhủ ị phân, v ịtrí của các node đư c xác đợ ịnh bằng prefix của ID Các ID trong Kademlia được biểu diễn theo cơ sở nh phân M i node chia cây nhị phân thành các ị ỗcây nh phân con liên tiị ếp mà không chứa ID của node và lưu ít nhất m t contact trongộ

mỗi cây con này Ví dụ, một node với ID là 3 có biểu diễn nhị phân 0011 trong không gian ID N=16 Do prefix vớ ội đ dài 1 là 0 nên nó cần biế ột m t node v i chớ ữ ố đầ s u tiên

là 1 Tương tự như v y, do prefix vớ ộ dài 2 là 00 nên node c n biậ i đ ầ ết m t node v i ộ ớprefix là 01 Prefix vớ ội đ dài 3 là 001, node cần biế ột node khác vớt m i prefix 000 Cuối cùng, do prefix vớ ội đ dài bằng 4 là 0011 nên nó cần biết node có prefix là 0010

Quy tắc này được minh họa trong Hình 1.14 dưới đây: