Khóa luận Tối ưu hóa Topology cho mạng ngang hàng có cấu trúc CHORD

ưu các cặp key/value ở các nút mà key được ánh xạ. Một nút sẽ chịu trách nhiệm lưu giữ một khóa k nếu nút đó là nút có định danh id nhỏ nhất và lớn hơn k. Một nút khi lưu giữ khóa k cũng sẽ được gọi là Successor(k). Hình 9. Lưu giữ key trong mạng Chord Tìm kiếm trong mạng Chord Khi một nút cần tìm kiếm một khóa có định danh id, nút đó sẽ tìm nút chịu trách nhiệm lưu giữ id đó. Nếu nút ở xa so với vị trí của nút lưu giữ id, nút có thể nhờ vào thông tin trong bảng Finger Table để định tuyến đến các nút xa hơn, từ đó dần dần biết được nút chịu trách lưu giữ id. Một ví dụ được chỉ trong hình 6, giả sử nút 3 muốn tìm successor của ID (hoặc còn có thể coi là khóa) 1. ID 1 thuộc khoảng [7, 3), tức là 3.finger[3].interval. nút 3 kiểm tra entry thứ 3 trong bảng định tuyến của nó, là 0. Bởi vì 0 trước 1, nút 3 sẽ hỏi nút 0 để tìm successor của 1. Quay trờ lại, nút 0 sẽ suy ra từ bảng định tuyển rằng successor của 1 chính là nút 1, và trả về nút 1 cho nút 3. Tham gia và ổn định mạng Trong 1 mạng động , thường xuyên có sự thay đổi với các nút 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 1 nút phải đc duy trì đúng Với mỗi khóa k, nút successor(k) có trách nhiệm quản lý k Khi tham gia vào một mạng Chord, một nút n cần chọn cho nó một định danh id và báo cho các nút bên cạnh biết sự tham gia của nó. Các nút Successor và Predecessor sẽ cần phải cập nhật thông tin về nút mới tham gia vào mạng. Nút n cũng cần khởi tạo bảng định tuyến Finger Table bằng cách tìm các nút mà Successor các id trong từng entry của Finger Table. Để mạng vẫn định tuyến đúng sau khi có sự tham gia của nút n, các nút cần thường xuyên chạy thuật toán ổn định mạng để cập nhật thông tin về nút bên cạnh ( hay nút hàng xóm). Một số nút sẽ có n trong bảng Finger Table, nên cần cập nhật một số entry của Finger Table. Cuối cùng là nút Successor của n sẽ chuyển một phần khóa mà bây giờ n là Successor(khóa), 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 nút chuẩn bị rời khỏi mạng, nó cần thông báo cho các nút bên cạnh biết để ổn định lại mạng. Nút đó cũng sẽ chuyển các khóa nó lưu giữ cho nút Successor của nó. Chương 2. Các nghiên cứu về tối ưu Chord Trong chương một, chúng ta đã được làm quen với Chord, cách xây dựng, cơ chế vận hành của Chord nói riêng và mạng ngang hàng có cấu trúc DHT nói chung. Đồng thời cũng thấy được tính ưu việt của Chord so với các cấu trúc khác. Tuy nhiên, vẫn tồn tại rất nhiều vấn đề của Chord và cả DHT – những vấn đề trở thành nhược điểm làm cho chi phí truyền thông cao, hiệu suất mạng giảm. Tiếp theo, khóa luận sẽ nói kỹ hơn về một số vấn đề mà mạng Chord gặp phải, phương hướng giải quyết cũng như tối ưu những vấn đề trên. Sau đó là một số nghiên cứu tiêu biểu cho vấn đề này. Tối ưu hóa trên Chord Cấu trúc Chord ngày càng được áp dụng cho nhiều ứng dụng ngang hàng. Vì vậy, việc tối ưu, khắc phục những nhược điểm của cấu trúc này là cần thiết. Có nhiều vấn đề đã được đề cập đến trong rất nhiều các bài nghiên cứu, báo cáo. Nhưng tập trung vào hai vấn đề chính: sự khác biệt về topo và tối ưu bảng định tuyến. Sự khác biệt về topo (Topology mismatch) Vấn đề khác biệt về topo nảy sinh ngày từ khi mạng ngang hàng có cấu trúc với bẳng băm phân tán được đưa ra. DHT xây dựng một mạng phủ bên trên mạng kết nối vật lý giữa các nút và sử dụng topo này trong việc xác định quan hệ, liên lạc, truyền dữ liệu. Mạng phủ định vị lại các nút trong một topology mới với địa chỉ là các giá trị băm. Sự phân tán của giá trị băm giúp cho mạng phủ được cân bằng ngẫu nhiên về không gian địa chỉ - tránh sự tập trung của nút và tài liệu trên toàn dải địa chỉ, đồng thời hỗ trợ việc bảo mật thông tin địa chỉ giữa các tầng cũng như các nút tham gia mạng, nhưng lại gây ra sự không đồng bộ về topo như trên. Theo đó, hai nút ở rất gần nhau về đường truyền vật lý có thể sẽ trở lên xa nhau trên dải địa chỉ của Chord và ngược lại. Trong các ứng dụng ngang hàng Chord, các truy vấn ngắn thường có tần suất lớn hơn các truy vấn dài do quá trình tìm kiếm ưu tiên các nút hàng xóm trước. Như vậy, hậu quả rõ rệt là với một truy vấn bất kỳ, thời gian đáp ứng cho truy vấn đó có thể rất lớn, hiệu suất của ứng dụng giảm. Một cách tiếp cận để giải quyết vấn đề Topology mismatch là dựa vào các đặc điểm vật lý. Đặc điểm vật lý chúng ta nói ở đây là vị trí của nút, địa chỉ của nút. Với các thông tin này, chúng ta có thể làm mới cấu trúc của mạng phủ sao cho phù hợp với mạng vật lý nhất. Nhưng giá phải trả cho phương pháp này là không nhỏ. Trước hết, cấu trúc gần với mạng vật lý trong nhiều trường hợp lại tỏ ra kém hiệu quả, đặc biệt là sự khó kiểm soát giao thông trên mạng tại từng vùng, từng điều kiện và thời điểm. Thứ hai, rất quan trọng, là làm mất đi tính trong suốt giữa các tầng. Tầng ứng dụng phải nắm được rất nhiều thông tin về tầng dưới không chỉ của máy local, các máy khác cũng phải cung cấp thông tin. Điều này ảnh hưởng đến an toàn giao thông mạng, các hình thức tấn công và hơn hết là sự riêng tư của những người tham gia mạng ngang hàng. Tối ưu bảng định tuyến (Finger Table) Một điểm cải tiến rất lớn lớn trong cấu trúc Chord (DHT nói chung) so với các thế hệ mạng ngang hàng trước chính là việc bổ xung thêm bảng định tuyến. Thay vì phát tràn các truy vấn hay thực hiện phát truy vấn theo một thuật toán ưu tiên nào đó như trong mạng ngang hàng không có cấu trúc, hoặc truy vấn tuyến tính trên dải địa chỉ băm của mạng có cấu trúc, bảng định tuyến giúp cho việc gửi các yêu cầu truy vấn diễn ra nhanh chóng, hiệu quả. Số lượng truy vấn phát ra từ nút tìm kiếm là duy nhất, và sau tối đa log2n bước chuyển tiếp, truy vấn sẽ tới đích. Cơ chế này dựa trên thuật toán tìm kiếm nhị phân, điều này lý giải tại sao entry thứ i trong bảng định tuyến sẽ lưu nút là successor của khóa có định danh cách định danh nút đang xét 2i định danh. Nhận thấy rằng, nút được chọn khi xây dựng từng entry của một bảng định tuyến là cố định, chỉ phụ thuộc vào topo hiện tại của mạng Chord. Sự thiếu mềm dẻo khi xây dựng bảng định tuyến cũng sẽ làm gia tăng thời trễ truy vấn, giảm chất lượng ứng dụng. Từ những nhận xét trên, đã có nhiều nghiên cứu nhằm cải tiến và tối ưu hiệu năng của Chord. Sau đây là một số nghiên cứu tiêu biểu – những nghiên cứu cũng được áp dụng trên nền Chord. Lựa chọn láng giềng gần (Proximity Neighbor Selection[5]) Nghiên cứu này tập trung cải thiện thuộc tính gần gũi trong mạng ngang hàng có cấu trúc nói chung. Căn cứ vào mạng liên kết tọa độ hai chiều ảo, những nút được xem là gần nhau được tập hợp lại vào một miền, các miền này kề sát nhau và phủ kín mặt phẳng tọa độ. Sau đó là quá trình ánh xạ (mapping) từ không gian mạng quan hệ sang không gian địa chỉ của DHT. Thông qua quá trình tìm kiếm các định danh miền tương ứng sử dụng thủ tục RPC trong Chord, các nút có thể nhận được danh sách hàng xóm của chúng một cách nhanh chóng theo cách thức phân tán hoàn toàn. Kết quả thu được thông qua chương trình mô phỏng mô hình với topo mở rộng đủ lớn chỉ ra rằng, cải tiến có một độ trễ lân cận trung bình thấp hơn phương pháp lấy ngẫu nhiên rất nhiều. Phương pháp này có hai điểm chính tập trung vào việc tối ưu hóa mạng Chord. Đầu tiên là sự chọn lọc láng giềng gần (Proximity Neighbor Selection - PNS), ở đó những láng giềng trong bảng định tuyến được lựa chọn dựa vào mức độ gần gũi của chúng với nút đang xét. Thứ hai là lựa chon tuyến đường gần, diễn ra khi lựa chọn điểm đích tiếp theo trong quá trình định tuyến tới một điểm đích riêng biệt, và cũng dựa trên mức độ gần gũi đã nêu. Phương pháp này giải quyết cả hai nhược điểm được nêu ở phần trước của Chord. Phân chia không gian liên kết hai chiều Trước tiên chúng ta sẽ xem xét cách xây dựng không gian liên kết hai chiều của các nút. Từ đó có thể đánh giá được mức độ gần gũi của các nút. Vì vậy, đây là một phần trọng trong khâu chuẩn bị, quyết định khá nhiều đến sự thành công của thuật toán. Hình 10. Bản đồ miền trong không gian hai chiều Thông qua thuật toán Vivaldi, mỗi nút sẽ lấy được tập các quan hệ trong mạng ảo hai chiều. Thuật toán Vivaldi sẽ ánh xạ một nút vào một tọa độ hai chiều (x, y) dựa vào công thức với nhiều tham số, trong đó có thời gian quay vòng (round-trip delay time - RTT) là thời gian đo đc tương tự như quá trình ping hay DNS và tọa độ của các nút trước đó. Kết quả của thuật toán là một mặt phằng tọa độ với các nút được ánh xạ vào một điểm trên đó. Tiếp theo là ánh xạ chia miền để xét quan hệ gần gũi. Với mỗi nút s được chọn là nút trung tâm, xét r cố định, các đường tròn có bán kính r, 2r, 3r… được định nghĩa như hình vẽ. Miền được định nghĩa như sau: hình vành khăn tạo bới phần cắt giữa đường tròn bán kính ir với đường tròn có bán kính (i-1)r chia thành 2i-1 miền diện tích bằng nhau và bằng PI*r2. Điều này chứng minh khá đơn giản. Các miền được đặt định danh bằng một cặp (i, j), trong đó i là số hiệu đường tròn nhỏ nhất chứa miền đó, j là thứ tự miền trong hình vành khăn đang xét. Thứ tự miền được đánh số theo chiều dương và từ góc 0o. Như vậy, mỗi nút sẽ có một bản đồ miền như mô tả. Từ vị trí của bản thân nút và vị trí tương đối của các nút xung quanh, thực hiện ánh xạ các nút hàng xóm vào các miền, các nút trong cùng một miền được xem là có quan hệ như nhau với nút trung tâm. Độ ưu tiên miền dựa vào tên định danh của miền, theo đó, giá trị i càng nhỏ, miền càng gần nút trung tâm. Việc chia miền giúp những cụm nút có khoảng cách và thuộc tính gần như nhau hợp lại, trợ giúp cho quá trình tìm kiếm và định tuyến phía sau. Tối ưu quá trình định tuyến Việc tìm kiếm các láng giềng gần diễn ra khá đơn giản. Mỗi nút đều lưu định danh miền mà nó thuộc về. Khi có yêu cầu tìm kiếm những nút láng giềng, nút được yêu cầu sẽ dựa vào định danh miền, xác định các nút nằm trong cùng miền đó. Như vậy dễ dàng tìm ra các nút láng giềng gần. Nếu nút đó 1 mình 1 miền, quá trình tìm kiếm bắt đầu với 6 miền lân cận. Quá trình tìm kiếm diễn ra cho đến khi tìm được ít nhất một nút. Những nút tìm được sẽ được add vào tập láng giềng gần. Thay đổi các đường dẫn trong bảng định tuyến là mục đích chính của nghiên cứu này. Trong Chord truyền thống, entry thứ i của là định danh của nút là successor của khóa k+2i với k là định danh nút hiện tại. Để có thể tận dụng được thời gian trễ và topo xây dựng bên trên, đồng thời tạo tính mềm dẻo cho việc lựa chọn, cải tiến đã chọn lại nút này bằng nút hàng xóm có định dạnh nằm trong khoảng [k+2i-1, k+2i) và gần nút đang xét nhất. Quá trình tìm kiếm nút hàng xóm gần đã được mô tả ở trên. Ưu điểm Cải thiện hiệu năng mạng, giảm độ trễ. Giữ nguyên cơ chế chạy của Chord truyền thống, đặc biệt là phần truy vấn. Nhược điểm Xây dựng không gian liên kết hai chiều theo thuật toán Vivaldi khá phức tạp. Tạo ra ánh xạ càng đầy đủ, càng gần thì chi phí xây dựng càng lớn. Quasi-Chord [7] Vấn đề sai khác topo mạng (topology mismatch) như đã được giới thiệu là một trong những vấn đề đáng kể nhất trong tối ưu mạng ngang hàng có cấu trúc. Nghiên cứu này đưa ra một mô hình mạng Chord mới với tên Quasi-Chord. Mô hình sử dụng hệ thống mạng định vị toàn cầu (global network position - GNP) để liên kết các nút trên tầng vật lý và sử dụng không gian Cantor, ánh xạ từ không gian hình học hai chiều sang một chiều theo đường gấp khúc. Sau đó xây dựng mô hình Quasi-Chord dựa trên các giá trị Cantor đó. Thực nghiệm mô phỏng cho thấy phương pháp thực sự đã làm giảm độ trễ và lưu lượng mạng với cùng một bộ truy vấn. Điểm đặc trưng nhất trong phương pháp là giải pháp thu thập điểm mốc (landmark clustering). Điểm mốc là một vài nút cố định trong hệ thống. Và mỗi nút khác đo thời gian quay vòng tới các điểm mốc, sắp xếp các điểm mốc đó theo thời gian đo được vào một chuỗi. Chuỗi điểm mốc này được dùng để mô tả vị trí của nút trong hệ thống, các nút có những chuỗi tương tự nhau sẽ là hàng xóm của nhau. Bản thu thập các điểm mốc là một bản phỏng đoán vị trí của các nút. Nó có thể không giúp đỡ đc gì trong tình trạng các nút ở rất gần nhau. Quasi-Chord xây dựng topo logic trên cơ sở là các thông tin về topo của tầng dưới. Vì thế, các nút gần nhau về ở tầng dưới thì cũng kề nhau ở tầng trên, điều mà có thể hạn chế mạnh mẽ giao thông mạng. Để xây dựng mô hình Quasi-Chord, cần ba bước. Đầu tiên, sử dụng mạng định vị toàn cầu để lấy các liên kết của nút trong không gian hình học P2P. Tiếp theo, sử dụng không gian Cantor, men theo đường gấp khúc để chuyển từ không gian hai chiều sang một chiều. Bước cuối cùng là xây dựng vòng Quasi-Chord thông qua các giá trị Cantor của các nút. Tính toán tọa độ của mỗi nút tham gia với GNP Quá trình ánh xạ và tính toán được chia thành hai giai đoạn: Tính toán với các điểm mốc: Trước tiên, chọn N điểm mốc từ L1 đến Ln. Phép đo đơn giản giữa các điêm mốc là thời gian quay vòng sử dụng gói tin ping ICMP và lấy giá trị nhỏ nhất trong một vài phép đo cho mỗi tuyến đường ở nửa dưới ma trân khoảng cách N*N đối xứng qua đường chéo của ma trận. Sử dụng những khoảng cách vừa đo được, các điểm mốc sẽ tính toán vị trí và liên kết trong không gian hình học S. Mục đích của phần này là tìm được tập hợp các vị trí, các liên kết cho N điểm mốc sao cho sự sai khác giữa khoảng cách đo được (thời gian quay vòng của gói tin ping) và khoảng cách tính toán trong không gian hình học S là nhỏ nhất. Hình 11. Tính toán với các điểm mốc Tính toán với nút thông thường Tương tự như trên nhưng áp dụng với một nút thông thường. Các giá trị thời gian quay vòng từ nút đến các điểm mốc được đo và lấy những giá trị nhỏ nhất. Từ những giá trị này, tính toán tìm vị trí của nút trên không gian S cũng với điều kiện sự sai khác giữa khoảng cách đo được và khoảng cách tính toán là nhỏ nhất. Hình 12. Tính toán với nút thông thường Ánh xạ không gian hai chiều sang một chiều sử dụng Cantor Đến đây, các nút đều đã được ánh xạ vào không gian hình học hai chiều. Do không gian địa chỉ của Chord là một chiều, việc ánh xạ từ không gian hai chiều sang một chiều là cần thiết. Để làm được điều đó, chúng ta sẽ đi theo đường rích rắc trên không gian hai chiều. Hình 13. Biểu đồ không gian Cantor với C=8 Giả sử không gian hình học hai chiều tựa ma trận vuông hai chiều như hình vẽ. Kích thước của ma trận phụ thuộc và tọa độ cực của các nút được ánh xạ trong phần trên. Xét đường đi rích rắc theo đường chéo xuất phát từ điểm trái dưới của ma trận như hình vẽ. Chúng ta sẽ được một thứ tự cho các nút có tọa độ giống chỉ số các ô trong ma trận. Đây chính là topo một chiều sẽ được ánh xạ lên vòng không gian địa chỉ trong phần sau. Xây dựng mô hình Quasi-Chord Vì các nút có giá trị Cantor tương tự nhau sẽ gần nhau trên tầng vật lý, chúng ta sẽ xây dựng vòng không gian địa chỉ Quasi-Chord dựa trên các giá trị Cantor này. Theo đường đi một chiều được chỉ ra ở phần trên, các nút theo thứ tự có tọa độ gần nhau sẽ trở thành hàng xóm trên vòng địa chỉ. Thay vì sử dụng hàm băm để lấy địa chỉ trong không gian DHT, Quasi-Chord sử dụng địa chỉ từ các giá trị Cantor. Giả sử có tối đa n nút tham gia vào mạng và kích thước ma trận vuông giới hạn bởi các tọa độ cực trị là C*C, địa chỉ nút trong mô hình này có m bit, thỏa mãn log2n≤ ≤ log2(C*C). Mỗi nút trong mô hình Quasi-Chord có hai bảng định tuyến. Một bảng theo chiều kim đồng hồ tương tự như Chord truyền thống, một bảng theo chiều ngược lại. Theo cách sắp xếp topo như trên, nút đầu và cuối trên vòng địa chỉ là rất xa nhau. Với Chord, hai nút này là gần nhau. Nhưng với Quasi-Chord, nếu xem xét hai nút là hàng xóm thì sẽ gây khó khăn khi truy cập cho những bước định tuyến phải vượt qua vị trí nối này. Vì thế Quasi-Chord quan niệm hai nút này không gần nhau. Nói cách khác successor của nút cuối không phải là nút đầu tiên và ngược lại. Hình 14: Bảng định tuyến giả định của N51 trong Quasi-Chord Bảng định tuyến thứ nhất xây dựng giống như trong Chord truyền thống. Điểm đáng chú ý là các định danh successor của các key mục tiêu trong mỗi entry đều không được nhỏ hơn định danh của nút đang xét. Ngược lại, với bảng thứ hai ngược chiều kim đồng hồ, định danh của successor không được lớn hơn định danh nút đang xét. Và tính key mục tiêu theo công thức (k – 2i-1) mod 2m thay vì (k + 2i-1) mod 2m. Khi nhận được một yêu cầu truy vấn, nút sẽ so sánh key của tài liệu lớn hay nhỏ hơn định danh nút, từ đó sử dụng bảng định tuyến xuôi hay ngược chiều kim đồng hồ tương ứng. Ưu điểm của Quasi-Chord thể hiện rất rõ ràng qua bước phân tích bên trên và kết quả thực nghiệm như biểu đồ. Tuy vậy vẫn tồn tại một vài nhược điểm: Mô hình thích hợp với số lượng nút và các nút trong mạng cố định. Cường độ vào ra cao của các nút trong mạng cao gây khó khăn việc ánh xạ địa chỉ. Xung đột có thể xảy ra khi ánh xạ nút vào không gian Cantor. Vẫn còn vấn đề tại điểm giao nhau giữa nút đầu tiên và cuối cùng trên vòng địa chỉ. Chương 3. Tối ưu Chord dựa trên lựa chọn độ trễ Chương hai cho chúng ta thấy được tổng quan những vấn đề, nhược điểm còn tồn tại trong mô hình mạng ngang hàng Chord và xem xét một số nghiên cứu nhằm tối ưu mạng Chord. Tư tưởng chủ đạo của những nghiên cứu này là ánh xạ mỗi nút tham gia vào một không gian ảo hai chiều, sử dụng thời gian trễ làm tham số; đánh giá mối quan hệ giữa các nút bằng quan hệ trên không gian hai chiều đó. Ưu điểm của phương pháp này là đánh giá mối quan hệ gần gũi tương đối sát so với trên mạng liên kết vật lý. Trong lựa chọn láng giềng gần, nhược điểm là khối lượng công việc khi nút tham gia mạng lớn, việc tạo mới và duy trì bản đồ quan hệ tại mỗi nút đòi hỏi nhiều tài nguyên. Vấn đề của Quasi-Chord là nguy cơ xung đột trên không gian ảo hai chiều và điểm nối giữa định danh lớn nhất và nhỏ nhất trên vòng địa chỉ. Trong chương ba, một giải pháp đơn giản sẽ được đề xuất cũng với mục đích tối ưu topo mạng phủ cấu trúc Chord. Giải pháp này cũng dựa trên thời gian quay vòng của gói tin ICMP, lựa chọn láng giềng và thay đổi bảng định tuyến. Đề xuất Để giải quyết vấn đề khác biệt giữa topo vật lý và topo logic thì các nút gần nhau tại tầng vật lý cần trở thành hàng xóm của nhau trên mạng phủ. Thêm nữa việc có được thông tin tầng dưới (địa chỉ ip, cổng) để xây dựng mạng phủ là không thể. Do đó, khoảng cách dựa vào thời gian trễ giữa các nút được xem là thước đo khả thi nhất đánh giá sự gần gũi giữa chúng. Trong Chord, vị trí của một nút khi tham gia vào mạng được sinh hết sức ngẫu nhiên và không có sự chọn lựa. Vì vậy, nếu cung cấp khả năng lựa chọn trong những quá trình này, sẽ tạo được kết quả chắc chắn có lợi hơn nhiều để cải thiện thời gian truy vấn. Từ những nhận xét trên, giải pháp được đưa ra chính là tập trung vào việc lựa chọn theo tiêu chí độ trễ. Giải pháp sẽ được chia thành hai giai đoạn. Đầu tiền, thực hiện lựa chọn vị trí gia nhập mạng cho nút mới từ một tập các định danh, tiêu chí lựa chọn là độ trễ thấp nhất đến các nút hàng xóm. Thứ hai, khi cập nhật lại bảng định tuyến cho nút sau quá trình vào ra của một số nút, tiếp tục lựa chọn điểm đến tiếp theo khi truy vấn trong tập chứa successor của khóa mục tiêu tại entry i và các lân cận của successor đó. Thời gian trễ từ nút đang xét tới các nút trong tập lựa chọn nhỏ nhất là tiêu chí lựa chọn. Chi tiết hai giai đoạn tối ưu như sau: Lựa chọn vị trí tham gia mạng Khi nút muốn tham gia vào mạng, thay vì cung cấp một định danh duy nhất, chúng ta sẽ cho phép một nút chọn một trong một tập định danh. Tập định danh này được sinh từ hàm băm với đầu vào là thông tin nút và tham số ngẫu nhiên do ứng dụng sinh ra. Tại mỗi vị trí với các định danh tương ứng, lựa chọn khoảng cách thời gian quay vòng nhỏ nhất với cả successor và predeccesor. Vị trí được chọn sẽ là vị trí có độ trễ đến một trong hai nút liền kề là nhỏ nhất. Thay đổi bảng định tuyến Bảng định tuyến sẽ được xây dựng ngay sau đó. Mỗi entry trong bảng định tuyến sẽ không được lấp đầy luôn bằng nút là successor của key mục tiêu tại entry i. Từ nút successor này, tìm kiếm về hai phía trên không gian một chiều Chord. Đo khoảng cách từ nút hiện tại tới các nút nằm trong tập các nút hàng xóm vừa tìm được, chọn nút có độ trễ ping nhỏ nhất. Dùng nút này đề lấp đầy entry đang xét. Việc lựa chọn vị trí sẽ làm cho các nút gần nhau theo thời gian trễ đo được đứng cạnh nhau trên vòng Chord. Quá trình thay đổi bảng định tuyến cũng sẽ làm giảm độ trễ trong việc chuyển tiếp một truy vấn. Như vậy, hai quá trình này hứa hẹn sẽ khắc phục được phần nào những vấn đề với mạng Chord đã được đề cập ở trên. Nội dung Chúng ta sẽ đi một cách chi tiết hơn vào các cải tiến, để từ một ứng dụng Chord truyền thống, có thể thực thi những cải tiến này một cách nhanh nhất. Trước tiên, cần có một vài thay đổi trong một số đối tượng so với Chord truyền thống: Hàm băm có thêm nhiều hơn một tham số. Trong Chord truyền thống, hàm băm nhận thông tin về nút, thường là địa chỉ ip và số hiệu cổng của tiến trình chạy. Như vậy, chúng ta sẽ có một giá trị băm duy nhất cho một nút. Theo yêu cầu của bài toán, chúng ta cần nhiều hơn một giá trị định danh từ một nút. Vì vậy, hàm băm cần nhận thêm một tham số là chỉ số nữa chẳng hạn. Đối tượng đo thời gian trễ giữa hai nút. Có thêm một đối tượng có thể gửi nhận các gói tin ICMP để đo khoảng thời gian quay vòng của các gói tin, từ đó tính khoảng cách một cách tương đối giữa các nút. Những sự thay đổi trong quá trình hoạt động của Chord để thực thi hai biện pháp tối ưu: Nút tham gia mạng Khi một nút muốn tham gia vào mạng, Chord truyền thống sẽ thực hiện băm để nhận một giá trị băm duy nhất. Sau đó thực hiện việc tham gia mạng cho nút tại vị trí đó. Với cải tiến, thay vì một giá trị băm được tính toán, một tập các giá trị băm được tính toán vào chuyển cho nút. Đây là tập giá trị có được từ việc băm thông tin nút và chỉ số phụ. Với mỗi giá trị địa chỉ, tìm successor và predeccessor cho địa chỉ đó. Thực hiện đo độ trễ từ nút đang xét đến hai nút này, lấy giá trị thời gian nhỏ nhất đại diện cho địa chỉ đó. Định danh được chọn sẽ có khoảng thời gian này là nhỏ nhất. Quá trình đo độ trễ, tính toán phải trong suốt. Có rất nhiều lựa chọn về điều kiện để chọn định danh, nhưng khoảng thời gian trễ nhỏ nhất là điều kiện đơn giản, đem lại hiệu quả khá tốt. Hình 15: Lựa chọn vị trí tham gia mạng Cho phép nút tham gia vào mạng với định danh đã được chỉ định như trong Chord truyền thống. Rõ ràng, cải tiến này sẽ làm tiêu tốn thời gian của nút khi tham gia vào mạng. Nói cách khác là khoảng thời gian trễ sẽ lâu hơn từ khi gửi yêu cầu tham gia và được tham gia thực sự. Xây dựng bảng định tuyến Sau khi để nút tham gia vào mạng, việc tiếp theo là xây dựng bảng định tuyến. Trước tiên, với entry thứ i trong bảng định tuyến, tính giá trị key mục tiêu (k + 2i-1) mod 2m, đồng thời tìm s là successor của key này. Giá trị ex được gọi là độ mở rộng trong xây dựng bảng định tuyến. Theo đó, xét ex nút liền trước, liền sau và bản thân s, ta được một tập 2*ex +1 nút. Điều kiện để lọc bớt các nút trong tập này là định danh nút phải nằm trong khoảng (k+2i-2, k+2i). Giới hạn này tránh sự xung đột và trùng lặp trong quá trình xây dựng định tuyến giữa các entry. Thực hiện đo thời gian trễ từ nút đang xét tới tập các nút vừa nêu, một danh sách độ trễ được trả về. Chọn nút có khoảng cách quay vòng là nhỏ nhất là successor của entry i. Những thay đổi trên mang tính cục bộ, chỉ là tác động vào quá trình tham gia mạng của nút mới và cập nhật bảng định tuyến trên Chord truyền thống. Vì thế, khả năng thực thi thêm giải pháp tối ưu vào ứng dụng Chord truyền thống là có thể làm được. Việc thay đổi bảng định tuyến sẽ không làm ảnh hướng đến thuật toán định tuyến của Chord truyền thống. Với cải tiến trên, có thể có những truy vấn mà số bước tìm kiếm cũng như thời gian đáp ứng tăng. Nhưng nhìn vào tổng thể, cải tiến đem lại tiềm năng rất lớn trong việc tiết kiệm băng thông và giảm thời gian đáp ứng khi truy vấn. Ưu nhược điểm Tiêu chí lựa chọn là có thời gian trễ gần nhất với hai nút hàng xóm mang tính cục bộ. Vì thế, xét một cách tổng thể khi so sánh với hai phương pháp trên, tất cả nút được ánh xạ vào không gian hai chiều trước, giải pháp tỏ ra kém hiệu quả hơn. Các quan hệ gần nhau trên vòng định danh mang tính cục bộ, các nút có thể bị chia thành các cụm nhỏ trên đó. Quasi-Chord với việc xếp đặt các nút lên vòng định danh khi lấy theo đường rích rắc trong không gian ảo hai chiều làm cho khoảng cách giữa các hàng xóm đều và trơn hơn. Giải pháp mang những đặc điểm của các nghiên cứu đã trình bày, đều hướng tới giải quyết vấn đề khác biệt trong topo mạng Chord và thay đổi bảng định tuyến dựa trên khoảng thời gian trễ giữa các điểm nút. Xong, mỗi phương pháp đều có những cách thực hiện riêng, khác nhau. Tất cả đều mang lại hiệu quả nhất định trong việc cải thiện hiệu năng, nhưng cũng tồn tại nhiều nhược điểm. Ưu điểm Đơn giản, dễ dàng nắm bắt và thực thi. Khá mềm dẻo, tùy biến các tham số tối ưu để phù hợp với điều kiện mạng cơ sở cũng như mục đích ứng dụng. Số lượng lựa chọn trong hai quá trình tối ưu đều có thể thay đổi dễ dàng. Nhược điểm Số lượng lựa chọn lớn sẽ gây trễ quá trình tham gia vào mạng của nút. Trong một số ít trường hợp, sự tối ưu không đem lại