Mạng CAN ( Content Addressable Network)

Mạng CAN[3] là một không gian n chiều. Không gian khóa được chia thành các vùng nhỏ cho các node trong mạng quản lý, mỗi node sẽ chịu trách nhiệm toàn bộ các khóa trong vùng quản lý nắm giữ. Mỗi khóa là một cặp (khóa, giá trị) , cặp (khóa,giá trị) này được ánh xạ vào node tương ứng. Các node trong mạng CAN sẽ duy trì thông tin định tuyến với các node hàng xóm của nó, là các node có vùng quản lý tiếp giáp với nhau. Các node hàng xóm này sẽ liên lạc với nhau để định tuyến tìm tới các node lưu giữ khóa ở xa.

Một mạng CAN với không gian khóa 2 chiều

Một node sẽ chịu trách nhiệm quản lý một vùng trong mạng gọi là “zone”, các khóa nằm trong vùng này sẽ được ánh xạ vào node đó. Một node khác cần tìm kiếm khóa k sẽ tìm tới node chịu trách nhiệm quản lý vùng có khóa k. Các node sẽ tìm kiếm khóa dựa vào các hàng xóm của nó. Hai node được gọi là hàng xóm của nhau nếu có chung một chiều quản lý trong vùng của mỗi node hay hai node có một chiều tiếp giáp nhau. Để duy trì tập các hàng xóm này thì mỗi node trong mạng CAN tạo ra một bảng định tuyến, bảng định tuyến sẽ lưu các node hàng xóm để khi cần sẽ định tuyến tới. Thông tin định tuyến sẽ được truyền đi liên tiếp các node hàng xóm của nhau cho tới khi tới được node có vùng quản lý khóa cần tìm kiếm.

Mô tả việc tìm kiếm trong mạng CAN

Một thông điệp CAN chứa tọa độ điểm đích. Sử dụng tập tọa độ vùng quản lý của các hàng xóm của nó, một node định tuyến thông điệp đến đích bằng cách sử dụng thuật toán tham lam chuyển thông điệp tới node nào có vùng quản lý gần nhất với tọa độ của điểm đích.

Một node W tham gia vào mạng CAN cũng giống như Chord cần biết được một node W’ đã tham trong mạng. Node W’ này đóng vai trò node giới thiệu node W vào trong mạng. Node W sẽ chọn một điểm P bất kì trong không gian mạng CAN để tham gia vào. Node W’ tìm xem node nào đang chịu trách nhiệm vùng có điểm P, giả sử là node V.

Quản lý vùng của CAN

Sau đó node W’ sẽ gửi thông điệp cho node V báo hiệu một node sẽ tham gia vào điểm P trong vùng quản lý của V. Vùng quản lý của node V sau đó sẽ được chia đôi ra thành 2 phần bằng nhau, một phần không có điểm P sẽ vẫn do node V quản lý, phần còn lại có điểm P và node W sẽ tham gia vào mạng tại điểm P và chịu trách nhiệm quản lý. Node W sẽ thừa kế lại toàn bộ bảng định tuyến lưu các node hàng xóm của V và gửi thông điệp tới các node này để xác định lại hàng xóm.

Mạng CAN cũng có khả năng chịu được những lỗi của node hoặc của mạng mà khi đó một node không thể tới được. Vấn đề này được giải quyết bằng cách: hàng xóm của node bị lỗi sẽ quản lý vùng của node bị lỗi, nhưng cơ sở dữ liệu các cặp (key, value) sẽ bị mất. Dữ liệu sẽ được cập nhật lại sau bởi người chủ của dữ liệu.