- Đánh giá các giải pháp tối ưu hóa topology cho mạng ngang hàng có cấu trúc. - Nghiên cứu một số phương pháp tối ưu hóa Topology mạng ngang hàng có cấu trúc Chord. - Mô phỏng và đánh giá các giải pháp. - Cấu trúc. - Chương 1: Mạng ngang hàng. - Mạng ngang hàng có cấu trúc sử dụng hệ thống DHT (Distributed Hash Table - Bảng băm phân tán). - 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ể, 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.. - Mỗi nút trên Chord có một định danh id và có khả năng duy trì liên kết 2 chiều với các nút đứng liền trước và liền sau nó theo chiều kim đồng hồ, tạo thành 1 mạch kiên kết vòng. - Thêm vào đó, mỗi nút sẽ lưu một bảng thông tin định tuyến gọi là Finger Table, cho phép nút đó định tuyến tới các nút ở xa.. - Tuy nhiên, ngoài ưu điểm tìm kiếm dữ liệu nhanh và cân bằng tải giữa các nút, nó còn bộc lộ một số nhược điểm để khắc phục điều đó tập trung vào 2 vấn đề chính: sự khác biệt về topo và tối ưu bảng định tuyến. - Trong ngang hàng Chord, truy vấn ngắn thường có tần suất lớn hơn các truy vấn dài do cơ chế ưu tiên trong quá trình tìm kiếm.. - Sự thiếu mềm dẻo khi xây dựng bảng định tuyến làm cho độ trễ truy vấn lớn, chi phí truyền thông cao.. - Chương 2 - Một số phương pháp tối ưu hóa Topology trên mạng ngang hàng có cấu trúc Chord.. - Lựa chọn láng giềng gần:. - Xây dựng không gian tọa độ 2 chiều.. - Mỗi nút trong mạng sẽ có một tọa độ tương ứng trong không gian tọa độ 2 chiều C và không gian tọa độ 2 chiều này sẽ được chia đều thành các vùng bằng cách sử dụng các vòng tròn đồng tâm.. - Tối ưu bảng định tuyến. - Áp dụng cho chiến lược xây dựng bảng định tuyến một cách linh hoạt với các nút có độ trễ thấp hơn mà định danh của chúng nằm trong khoảng gần nút đang xét nhất.. - Việc phân hoạch để tạo ra không gian tọa độ 2 chiều giúp các nút mạng có được tọa độ của mình và có thể dự đoán được RTT mà không cần thực hiện việc thăm dò trên toàn mạng.. - Dựa vào toạ độ 2 chiều của mạng ảo, các nút gần nhau sẽ được nhóm vào trong cùng một miền và miền kế nhau sau khi ánh xạ từ không gian toạ độ của mạng sang không gian định danh của DHT, chính vì vậy mà quan hệ gần gũi của các nút mạng trong hệ thống sẽ không bị thay đổi.. - Nhờ vào việc tìm kiếm trên vùng id tương ứng bằng RPC trong Chord, các nút sẽ tìm được láng giềng gần một cách nhanh chóng trong vùng phân tán đó. - Từ đó giảm được độ trễ tìm kiếm trên mạng.. - Vivaldi là một thuật toán giúp các nút trong mạng có thể tự dự đoán RTT. - Đây là một thuật toán phân tán không yêu cầu hạ tầng mạng và không phụ thuộc vào các nút.. - Không gian tọa độ.. - Xây dựng không gian tọa độ thỏa mãn: khoảng cách trực tiếp giữa hai nút A và C phải nhỏ hơn hoặc bằng với khoảng cách dọc theo đường đi từ A đến B và B đến C.. - Sử dụng tọa độ 2-chiều với các hàm khoảng cách Euclide chuẩn.. - Fij là vector lực của lò xo giữa các nút i và j mà nó tác dụng trên nút i. - Điều chỉnh lại tọa độ của i theo hướng của lực:. - Khó khăn chính trong việc thực hiện Vivaldi là đảm bảo rằng nó hội tụ đến tọa độ mà dự đoán được RTT tốt. - Để giải quyết điều này, Vivaldi sẽ điều chình tỷ lệ hội tụ bằng bước nhảy δ: giá trị δ lớn thì Vivaldi dùng để điều chỉnh tọa độ trong bước nhảy lớn. - Tối ưu Chord dựa vào giải thuật Vivaldi.. - Trước hết, các nút trong hệ thống sẽ tự cập nhật tọa độ của mình đến tọa độ mới theo thuật toán Vivaldi sao cho việc dự đoán RTT chính xác nhất.. - Một nút A sẽ duy trì một danh sách các nút ứng cử viên của nó. - Việc lựa chọn Successor của nút A sẽ thực hiện đo khoảng cách tứ nó đến các nút ứng viên để tìm ra nút có RTT ngắn nhất. - Khi có một nút mới tham gia vào hệ thống, thuật toán Vivaldi sẽ được thực hiện để các nút lại tự cập nhật tọa độ của mình.. - Ngoài ra cần thay đổi Chord để có thể sử dụng Vivaldi đó là: Bất cứ khi nào một nút gửi RPC yêu cầu hoặc trả lời nút khác, nó sẽ gửi tọa độ của nó vào trong RPC đó. - Dựa vào thông tin có trong RPC, Vivaldi sẽ tính độ trễ tới các nút khác. - Ngoài ra, bất cứ khi nào các nút trao đổi thông tin định tuyến, chúng sẽ gửi thêm tọa độ cũng như địa chỉ IP của chúng. - Do đó Chord luôn luôn biết tọa độ của nút mà không phải “nói chuyện” với nút đó trước.. - Tính hiệu quả của thuật toán: Mỗi nút cung cấp thông tin để một nút khác cập nhật tọa độ của nó.. - Do vậy, khi có những thay đổi cấu trúc topology thì các nút sẽ cập nhật tọa độ của chúng một cách tự nhiên và phù hợp.. - Vivaldi đã giúp Chord cải tiến được hiệu năng của mạng, tối ưu trong quả trình tìm kiếm lặp.. - Mô phỏng 3.1. - Đánh giá tính hiệu quả của các giải pháp cũng như đánh giá được những cải tiến về hiệu năng của các giải pháp tối ưu trên mạng Chord thông các độ đo như: Độ trễ tìm kiếm, băng thông sử dụng, tỉ lệ tìm kiếm thành công.. - Đánh giá ảnh hưởng của kích thước mạng tới độ trễ tìm kiếm và băng thông sử dụng của các nút cũng như tỉ lệ tìm kiếm thành công ứng với từng giao thức.. - Đánh giá ảnh hưởng của topo mạng tới độ trễ tìm kiếm ứng với từng giao thức.. - Thực nghiệm mô phỏng. - Kích thước mạng lần lượt là nút.. - Ma trận độ trễ tương ứng với từng kích thước mạng được xây dựng từ tập dữ liệu King. - Độ trễ trung bình giữa các nút là 159ms.. - Kết quả mô phỏng:. - Băng thông sử dụng: là tổng số byte gửi đi bởi tất cả các nút (bao gồm cả dữ liệu điều khiển) chia cho khoảng thời gian trung bình mà các nút tồn tại trong hệ thống. - Băng thông sử dụng. - Hình 3.2: Băng thông sử dụng. - Dựa vào đồ thị hình 3.2 với kích thước mạng tăng lên thì băng thông sử dụng của Chord và ChordPNS cũng tăng lên. - Nguyên nhân đó là do khi thực hiện Vivaldi, thông tin các nút được trao đổi trên mạng được gửi đi trong các message của RPC chính vì vậy nó sẽ không làm tăng chi phí của mạng.. - Độ trễ tìm kiếm trung bình: Là thời gian trung bình mà các nút sử dụng trong các tìm kiếm thành công.. - Độ trễ tìm kiếm trung bình. - Độ trễ (ms). - Hình 3.3: Đồ thị về độ trễ tìm kiếm trung bình. - Dựa vào đồ thị hình 3.3 chúng ta thấy rằng với số nút trong mạng tăng gấp đôi thì độ trễ tìm kiếm trung bình của chord, chordPNS và Vivaldi cũng tăng lên. - Tuy nhiên đối với Chord, độ trễ tìm kiếm tăng 1.5 lần khi kích thước mạng tăng gấp đôi trong khi đó với ChordPNS và Vivaldi, độ trễ tìm kiếm chỉ tăng tuyến tính. - Ngoài ra, so với Chord, ChordPNS, Vivaldi có độ trễ thấp hơn ứng với cùng số nút như nhau. - Việc chọn nút làm successor có khoảng cách ngắn nhất trong danh sách các nút ứng viên làm láng giềng gần đã làm giảm đáng kể độ trễ tìm kiếm. - Đối với lựa chọn láng giềng gần việc ánh xạ các nút vào các miền đã cải thiện đáng kể việc lưu thông tin trong bảng định tuyến và rút ngắn thời gian định tuyến. - Quá trình tìm kiếm sẽ được thực hiện trên 6 miền lan cận và việc chọn định danh nút hàng xóm sẽ nằm trong khoảng [k+2 i-1 , k+2 i. - Tuy băng thông sử dụng mạng là tương đương nhau so với lựa chọn láng giềng gần (trong đồ thị hình 3.2) nhưng Vivaldi đã cải thiện đáng kể độ trễ tìm kiếm trung bình của mạng. - Dựa vào đồ thị hình 3.3 có thể thấy rằng độ trễ tìm kiếm trung bình của mạng đã giảm hơn ½ lần. - Có được kết quả như vậy là do Vivaldi thực hiện cập nhật lại tọa độ từ đó tối ưu được độ trễ dự đoán.. - Đây là đại lượng chỉ ra sự sai khác giữa độ trễ dự đoán và khoảng cách giữa cặp nút trong hệ thống.. - Với kích thước mạng tăng lên, đồ thị hình 3.4 cho thấy sai số tương đối giảm dần. - Điều này cho thấy rằng với kích thước mạng càng lớn khả năng hội tụ của các nút về những vị trị mới lý tưởng càng cao. - Như vậy khả năng dự đoán RTT của các nút càng chính xác.. - Tỉ lệ tìm kiếm không thành công: là tỉ số giữa số lần tìm kiếm không thành công chia cho tổng số lần tìm kiếm. - Tỉ lệ tìm kiếm không thành công. - Hình 3.5: Đồ thị so sánh tỉ lệ tìm kiếm không thành công.. - Đồ thị hình 3.5 cho ta thấy rằng, tỉ lệ tìm kiếm không thành công của Chord, ChordPNS và Vivaldi khá thấp (chưa đến 1.5. - Ngoài ra chúng ta còn thấy rằng ChordPNS (tương đương Vivaldi) có tỉ lệ tìm kiếm thành công cao hơn Chord và khi kích thước mạng tăng lên thì tỉ lệ tìm kiếm thành công cũng tăng theo. - Có được điều này là do khi kích thước mạng tăng lên thì xác suất tìm kiếm của các giải pháp tối ưu cũng tăng theo.. - Thực nghiệm 2: Tăng khoảng cách giữa các nút trong mạng cùng kích thước.. - Cấu hình mô phỏng:. - Kích thước mạng 1024 nút.. - Ma trận độ trễ được xây đựng lại dựa trên ma trận trong thực nghiệm 1, thay đổi khoảng cách giữa từng cặp nút bằng cách gia tăng độ trễ giữa chúng lần lượt là giây).. - Khoảng cách tăng (s). - Hình 3.6: Độ trễ tìm kiếm trung bình của mạng 1024 nút. - Dựa vào hình 3.6 với kích thước mạng 1024 nút, khi tăng khoảng cách từng cặp nút thì độ trễ tìm kiếm trung bình của Chord và ChordPNS tương ứng cũng tăng lên. - Điều này cho thấy rằng độ trễ tìm kiếm trung bình của Chord và ChordPNS phụ thuộc vào khoảng cách giữa các nút. - Vì vậy việc xây dựng được mạng phủ phù hợp sẽ giàm được khá nhiều chi phí tìm kiếm.. - Thực nghiệm 3: Tăng khoảng cách trong các mạng có kích thước khác nhau Cấu hình mô phỏng:. - Kích thước mạng sử dụng lần lượt là . - Độ trễ tìm kiếm trung bình:. - Hình 3.7: Độ trễ tìm kiếm trung bình khi tăng khoảng cách theo hệ số.. - Đồ thị hình 3.7 cho thấy rằng khi hệ số a=1.5 và a=2 (tăng khoảng cách 1.5 và 2 lần), tương ứng với từng kích thước mạng độ trễ tìm kiếm trung bình tăng nhanh ứng với Chord và ChordPNS.. - Đối với Vivalđi, độ trễ tìm kiếm tăng không đáng kể.. - Nhận xét: Trong thực nghiệm mô phỏng 2 và 3, khi tăng khoảng cách giữa các nút nhìn chung Chord và ChordPNS có độ trễ tìm kiếm tăng nhanh. - Sự khác biệt này là do Vivaldi thực hiện cập nhật lại tọa độ của các nút về tọa độ mong muốn, giảm thiểu độ trễ tìm kiếm.. - Trong mạng ngang hàng không có cấu trúc, một nút mới sẽ chọn ngẫu nhiên một số các nút hiện có của các hệ thống để làm các láng giềng của nó, trong khi ở mạng ngang hàng có cấu trúc, một nút mới sẽ nhận được một giá trị nhất định được xác định bởi hàm băm và xây dựng kết nối với các nút khác dựa trên các quy tắc cụ thể của DHT. - Tối ưu topology trên mạng có cấu trúc khác như Pastry, Kademlia, Tapestry dựa vào giải thuật Vivaldi.. - Đánh giá các phương pháp lựa chọn láng giềng trên mạng ngang hàng có cấu trúc: Lựa chọn láng giềng gần, lựa chọn định danh gần (Proximity Identifier Selection).