Phần 2 Flat naming

2.1. Khái niệm flat naming

Định danh không có cấu trúc (flat name): Các tên được đặt ngẫu nhiên, phi cấu trúc và không chứa bất kì một thông tin nào về access point của thực thể tương ứng.

2.2. Các phương pháp xác định thực thể khi biết định danh

Vấn đề đặt ra là làm thế nào để từ định danh có thể xác định được vị trí của thực thể đó. Sau đây là một số các giải pháp cho vấn đề trên.

2.2.1 Các giải pháp đơn giản

Chúng ta sẽ xem xét hai giải pháp đơn giản cho việc xác định vị trí của thực thể, hai giải pháp nàyđược áp dụng cho mạng local network

A, Giải pháp Broadcast và Multicast

Với giải pháp này việc xác định vị trí của thực thể bằng cách gửi gói tin chứa đựng định danh củathực thể cho tất cả các máy, và mỗi máy sẽ được yêu cầu kiểu tra xem liệu đó có phải là thực thể của nó ko. Chỉ có duy nhất một máy có thể cung cấp điểm truy nhập bằng cách gửi trả lời tới địa chỉ của máy yêu cầu truy nhập. Nguyên lý này được dùng trong giao thức ARP (Internet Address Resolution Protocol) để tìm địa chỉ tầng liên kết dữ liệu của một máy khi biết địa chỉ IP của máy đó.

 Kiểu truyền dẫn này cho phép truyền gói tin từ một địa điểm tới tất cả các host trên một mạng con mà không quan tâm đến việc một số host không có nhu cầu nhận nó. Khi mạng được phát triển thì Broadcasting trở nên không có hiệu quả, gói tin yêu cầu sẽ gây lẵng phí đối với băng thông của mạng, và các máy được gửi yêu cầu sẽ không trả lời do tắc nghẽn mạng.

 Một giải pháp cho vấn đề này là sử dụng multicasting. Một địa chỉ Multicast cho phép phân phối dữ liệu tới một tập hợp các host đã được cấu hình như những thành viên của một nhóm Multicast trong các mạng con phân tán khác nhau. 

-> Đây là phương pháp truyền dẫn đa điểm, trong đó chỉ các host có nhu cầu nhận dữ liệu mới tham gia vào nhóm. Điều này hạn chế tối đa sự lãng phí băng thông trên mạng, hơn nữa còn nhờ cơ chế gửi gói dữ liệu Multicast mà băng thông được tiết kiệm triệt để. Với Multicast thỉ nó hạn chế số host nhận yêu cầu. Khi một host gửi thông điệp tới địa chỉ multicast, thì lớp mạng cung cấp một dịch vụ chuyển tiếp gói tin tới tất cả các thành viên của nhóm đó

->  địa chỉ multicast có thể được sử dụng đê xác định địa chỉ cho 1 nhóm.

Nhược điểm của Broadcast và multicast : không thể mở rộng quy mô ra ngoài các mạng nội bộ ; đòi hỏi tất cả các tiến trình phải đợi nghe các yêu cầu về vị trí.

B, Forwarding pointer (gửi chuyển tiếp con trỏ)

Đây là một phương pháp dùng để xác định vị trí thực thể di động. Khi một thực thể di chuyển từ A đến B, nó sẽ để lại A một tham chiếu tới vị trí mới của nó tại B. Việc định vị thực thể có thể được thực hiện hoàn toàn trong suốt với client bằng cách là lần theo chuỗi con trỏ. Điểm tiến bộ của phương pháp này là nó đơn giản, nhưng phương pháp này có nhiều nhược điểm.

Nếu không có phương pháp đặc biệt thì chuỗi con trỏ của một nút thường xuyên di chuyển sẽ trở nên dài đến nỗi việc định vị nó trở nên tốn kém. Tất cả các địa điểm trung gian trong chuỗi đều phải giữ phần của mình trong chuỗi con trỏ chuyển tiếp. Rủ ro do đứt chuỗi kết nối, chỉ cần mất một con trỏ do bất kì lí do gì thì cũng đủ để không thể tới thực thể đang cần định vị nữa.

Tóm lại phương pháp này khó mở rộng quy mô về địa lý do chuỗi con trỏ dài khó chống lại được các sự cố và làm tăng độ trễ của mạng khi phải lần theo chuỗi con trỏ. Để giải quyết vấn đề này cần làm giảm chuỗi của con trỏ và tạo ra một vùng nhớ để lưu trữ vị trí hiện tại của con trỏ.

2.2.2 Cách tiếp cận home-based

Việc sử dụng các phương pháp đơn giản khó thực hiện có hiệu quả với những mạng rộng lớn. Và khi chuỗi tìm kiếm dài và liên kết có thể bị mất thì việc chỉ dẫn của forwarding pointer là một vấn đề. Một giải pháp để khắc phục tình trạng này đó là home-based.

Phương pháp này sử dụng để lưu trữ vị trí hiện tại của thực thể và vị trí lưu trữ thường là nơi mà thực thể được tạo ra. 

Nhược điểm của phương pháp này là nó phải gửi gói tin thông báo vị trí hiện tại tới vị trí ban đầucủa thực thể điều đó làm tăng độ trễ của việc truyền thông. Và nhược điểm nữa là vị trí home luôn luôn phải cố định và tồn tại nếu không việc liên hệ với thực thể là điều không thể. Và nghiêm trọng hơn nếu thực thể đó chuyển đến một vị trí khác một cách vĩnh viễn.

->  Để khắc phục tình trạng này bằng cách đăng kí với dịch vụ đặt tên và đó sẽ là nơi mà yêu cầu tìm kiếm sẽ tìm đầu tiên.

2.2.3 Bảng băm phân tán-DHT

Định nghĩa:- Bảng băm phân tán (tiếng Anh: Distributed hash tables - DHT) là một lớp các hệ thống phân tán không tập trung, cung cấp một dịch vụ tra cứu tương tự như một bảng băm: các cặp (khóa, giá trị) được lưu trữ trong DHT, và bất kỳ nút mạng tham gia nào cũng có thể lấy được giá trị liên kết với một khóa cho trước một cách hiệu quả.

- Nhiệm vụ lưu trữ ánh xạ từ khóa tới giá trị được phân tán giữa các nút, bằng cách đó sẽ giảm bớtlỗi nếu có thay đổi trong một tập hợp các nút tham gia. Điều này cho phép sử dụng DHT cho một số lượng cực lớn các nút mạng và xử lý việc vào, ra, và lỗi các nút mạng một cách liên tục.

Hệ thống Chord: Có nhiều hệ thống dựa theo mô hình DHT(như CAN, Pastry, Viceroy…), trong đó hệ thống Chord đại diện cho nhiều hệ thống trong số đó. Chord dùng một không gian định danh m-bit để gán các định danh được chọn ngẫu nhiên cho các nút, cũng như khóa cho các thực thể cụ thể. Các thực thể có thể là bất cứ cái gì, file, tiến trình,…Số bit m thường là 128 hoặc 160 tùy theohàm băm sử dụng.

Các nút được tổ chức thành một vành logic. Trong đó mỗi nút được gán một định danh duy nhất ngẫu nhiên gồm m bit. Mỗi thực thể được gán một khóa duy nhất dài m bit. Thực thể có khóa k nằm dưới quyền kiểm soát của nút có định danh id nhỏ nhất mà có giá trị không nhỏ hơn k. Nút đó được gọi là successor (nút liền sau) của k và được kí hiệu là succ(k).

Vấn đề chính của các hệ DHT là làm sao để phân giải để từ một khóa k lấy được địa chỉ của succ(k). Giải pháp dễ thấy nhưng không thể mở rộng quy mô được là để cho mỗi nút p lưu vết của nút liền sau succ(p+1) cũng như nút liền trước pred(p) của p.

Giải pháp của Chord là finger table. Mỗi nút p giữ một bảng finger FT¬p[] chứa tối đa m entry: FTp[i]=succ(p+2i-1)

Trong đó FTp[i] trỏ tới nút đầu tiên đứng sau p và cách p ít nhất 2i-1 vị trí. Để tra cứu một khóa k, nút p tìm trong bảng finger của mình chỉ số j lớn nhất thỏa mãn FTp[j] ≤ k rồi chuyển tiếp yêu cầu tới nút q=FTp[j].

q= FTp[j] ≤ k < FTp[j+1].

 Nếu không tìm thấy j, nghĩa là p < k < FTp[1], thì p chuyển tiếp yêu cầu tới nút q=FTp[1].

Vấn đề của hệ thống dựa DHT là tổ chức logic của các nút trong mạng overlay có thể dẫn đến việc thông điệp gửi tán loạn trong mạng Internet nằm bên dưới: khi nút k và nút succ(k) có thể ở rất xa nhau. 

Tham gia một hệ thống DHT-chẳng hạn như Chord là tương đối đơn giản. Giả sử nút p muốn tham gia, nó chỉ đơn giản là liên lạc với một nút bất kỳ trong hệ thống hiện có và yêu cầu tra cứu. Một khi nút này được xác định, p có thể chèn nó vào vòng Chord.

Một trong những vấn đề có thể xảy ra với các hệ thống như Chord là yêu cầu có thể được chuyển thất thường trên internet. Như vậy để giảm thiểu việc phải chuyển qua 3 vùng rộng lớn thì  thiết kế những hệ thống DHT yêu cầu dùng một tài khoản vào mạng chung này.

2.2.4. Hierarchical Approaches (tiếp cận phân cấp)

Xây dựng một cây tìm kiếm phân cấp và thực hiện phân miền ở các mức khác nhau. Cụ thể ta có thể xây dựng như sau:

Một mạng được chia thành một tập hợp các miền . Trong đó một miền ở tầng cao nhất phủ toàn bộ mạng. Mỗi miền được chia tiếp thành các miền con, mỗi miền ở tầng thấp nhất gọi là miền lá, thường ứng với 1 mạng nội bộ trong mạng máy tính hoặc 1 cell trong một mạng điện thoại di động. Tập hợp các miền nói trên được biểu diễn bởi cây tìm kiếm, quy mô lớn trong đó, mỗi miền được đại diện 1 nút trong thư mục miền tầng cao nhất được đại diện 1 nút thư mục gốc.

2.2.4.1. Quá trình tra cứu thông tin một thực thể.

- Để lưu dữ thông tin về địa điểm của một thực thể E hiện đang nằm tại miền D, địa chỉ của E được lưu trong một location record đặt tại nút lá D. Các nút tổ tiên của D cũng ghi 1 location record về E trong đó con trỏ tới một nút con mà cây con đó có gốc tại nút con đó lưu trữ địa chỉ của thực thể E. Nút gốc có thông tin về tất cả các thực thể.

Ví dụ: Thực thể E có ở 2 miền giá trị D1 và D2 . 

Quá trình tra cứu 1 thực thể trong cây tìm kiếm.

Quy trình tra cứu bắt đầu từ nút lá nơi mà client đang cứ trú. Nếu nút đó biết về E thì theo con trỏ đi xuống cây con. Nếu không đi ngược lên nút cha, đi lên cho tới khi nào có 1 nút biết về E, sau đó đi theo các con trỏ đi xuống tới khi gặp nút lá chứa địa chỉ của thực thể E 

Về nguyên tắc, thực thể được tìm kiếm ngày càng tăng. Khu vực tìm kiếm được mở rộng mỗi lần yêu cầu tra cứu được chuyển tiếp đến một nút tiếp theo phương hướng cấp cao hơn.Trong trường hợp xấu nhất, tìm kiếm vẫn tiếp tục cho đến khi yêu cầu đến nút gốc. Bởi vì nút gốc có một hồ sơ vị trí cho mỗi thực thể, yêu cầu có thể sau đó chỉ cần chuyển tiếp dọc theo 1 con đường đi xuống của một con trỏ trong các nút lá

2.2.4.2. Quy trình thêm 1 thực thể vào hệ thống

Quy trình thêm 1 thực thể vào hệ thống thì cũng tương tự như quá trình tra cứu, quá trình được mô phỏng như sau:

Như hình 4.2 ở trên ta thấy rằng thực thể E được sao chép ở 2 miền D1  và D2 nhiệm vụ là phải chèn được địa chỉ của nó. Việc chèn thì được bắt đầu từ nút lá ở đây là ở thư mục D. khi đó nó sẽ gửi thông điệp chèn cho các nút trên giả sử tới một M nút tại nút M thì nó lưu trữ một con trỏ vào hồ sơ trỏ tới E. Rồi sau đó nó đề cập tới nút đã gửi yêu cầu chèn tại nút đó cũng tạo ra hồ sơ chứa vị trí E quá trình cứ diễn ra như vậy cho tới khi con trỏ trỏ tới nút lá mà ở đó yêu cầu chèn được khởi xướng.

2.2.4.3. Quy trình xóa 1 thực thể ra khỏi hệ thống 

Việc xóa 1 thực thể ra khỏi hệ thống thì cũng diễn ra tương tự, ( ở đây ta giả sử vẫn xét thực thể E ở miền D). Khi 1 địa chỉ E là 1 thực thể cần phải loại bỏ ở miền D như vậy tại D nó sẽ ra một thông báo phải loại bỏ địa chỉ từ vị trí nó tới E, như vậy khi đó thì vị trí của E sẽ ko còn ở trong D nữa hồ sơ có thể được loại bỏ.Như vậy con trỏ trỏ từ cha của D để ghi vị trị của E cũng trống rỗng do đó hồ sở cũng được loại bỏ quá trình được diễn ra tương tự cho đến khi không còn nút nào chứa hồ sơ địa chỉ E nữa.