Luận Văn Tối ưu hóa topology cho mạng ngang hàng có cấu trúc chord

Tóm tắt

Ngày nay, Internet đã thực sự phát triển và đi sâu vào đời sống của mỗi con người. Khả năng chia sẻ những tài nguyên lớn một cách nhanh chóng và hiệu quả luôn nhận được quan tâm từ những người nghiên cứu cũng như sử dụng Internet. Với những đặc điểm phù hợp, mạng ngang hàng, đặc biệt là mạng ngang hàng có cấu trúc ngày càng được sử dụng phổ biến cho các ứng dụng nêu trên. Tuy nhiên, bên cạnh những ưu điểm, mạng ngang hàng có cấu trúc cũng bộc lộ những hạn chế nhất định, làm tiêu tốn băng thông và khả năng của mạng cũng như ứng dụng. Vì thế, vấn đề tối ưu mạng ngang hàng có cấu trúc, khắc phục những nhược điểm còn tồn tại trở lên cần thiết.

Khóa luận sẽ trình bày một giải pháp tối ưu mạng ngang hàng cấu trúc Chord - một giao thức của mạng ngang hàng có cấu trúc - dựa trên thời gian trễ. Giải pháp tập trung giải quyết vấn đề khác biệt về topo (topology mismatch) qua hai quá trình: lựa chọn vị trí tham gia mạng của nút và tối ưu bảng định tuyến. Tiêu chí dùng để tối ưu chính là thời gian trễ giữa các nút tham gia. Giải pháp này đã được thử nghiệm trên chương trình mô phỏng với môi trường mạng ảo có thời gian trễ gần giống với Internet. Kết quả cho thấy, giải pháp tối ưu đã đem lại hiệu quả với việc làm giảm thời gian trễ và chi phí truyền thông trong các truy vấn tìm kiếm. Theo đó, hiệu năng của mạng và ứng dụng cũng được nâng lên.





Mục lục

Mở đầu 1

Chương 1. Tổng quan 3

1.1. Mạng ngang hàng 3

1.2. Phân loại mạng ngang hàng 6

1.2.1. Hệ thống ngang hàng lai (Hybrid Peer-to-peer System) 6

1.2.2. Mạng ngang hàng thuần túy (Pure Peer-to-peer System) 7

1.2.3. Kiến trúc siêu ngang hàng (Super-peer Architecture) 8

1.2.4. Mạng ngang hàng có cấu trúc (Structured) 10

1.3. Cấu trúc Chord 12

1.3.1. Mô hình mạng Chord 13

1.3.2. Ánh xạ khóa vào một nút trong Chord 14

1.3.3. Tìm kiếm trong mạng Chord 14

1.3.4. Tham gia và ổn định mạng 15

Chương 2. Các nghiên cứu về tối ưu Chord 16

2.1. Tối ưu hóa trên Chord 16

2.2. Lựa chọn láng giềng gần (Proximity Neighbor Selection[5]) 17

2.3. Quasi-Chord [7] 20

Chương 3. Tối ưu Chord dựa trên lựa chọn độ trễ 24

3.1. Đề xuất 24

3.2. Nội dung 25

3.3. Ưu nhược điểm 27

Chương 4. Mô phỏng và đánh giá 29

4.1. Chương trình mô phỏng 29

4.1.1. Kiến trúc mạng mô phỏng 29

4.1.2. Dữ liệu 31

4.1.3. Các đối tượng 32

4.1.4. Thực thi 34

4.2. Kết quả và đánh giá 37

4.2.1. Hiệu quả so với Chord truyền thống 37

4.2.2. Hiệu quả khi thay đổi tham số 38

Chương 5. Kết luận 42

5.1. Kết luận 42

5.2. Hướng phát triển tiếp theo của đề tài 43

Tài liệu tham khảo 44

Phụ lục A 45


Mở đầu

Trong những năm gần đây, công nghệ ngang hàng (peer-to-peer - P2P) hay mạng ngang hàng đã trở nên phổ biến trong các nghiên cứu về lĩnh vực Internet. So với các mô hình mạng khác, mạng ngang hàng có nhiều ưu điểm như khả năng mở rộng, không tồn tại điểm chết, khả năng của hệ thống tỉ lệ với số lượng máy tham gia, Tất cả những đặc điểm trên đã tạo lên công nghệ P2P và các ứng dụng ngang hàng liên quan. Nhiều ứng dụng lớn đã và đang được xây dựng trên mạng ngang hàng như FreeNet, Napster, Gnutella, BitTorrent, eMule

Mạng ngang hàng có cấu trúc sử dụng giải thuật DHT (Distributed Hash Table – bảng băm phân tán) tạo nên một mạng phủ (overlay) trên mạng liên kết vật lý. Giải thuật này định nghĩa liên kết giữa các nút mạng trong mạng phủ theo một cấu trúc cụ thể, đồng thời 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 đều được kết nối với một tập các nút khác gọi là tập nút láng giềng. Chord là một giao thức của mạng ngang hàng có cấu trúc với không gian địa chỉ một chiều dạng vòng. Mạng ngang hàng cấu trúc Chord ngày càng thể hiện nhiều ưu điểm như khả năng mở rộng, cân bằng tải, định tuyến, . Giống như những giao thức trên mạng có cấu trúc khác, mỗi nút trong Chord xây dựng một bảng định tuyến giúp cho việc tìm kiếm thông tin giảm từ O(N) với N là số lượng tối đa nút trong mạng, xuống còn O(log2N).

Trong mạng ngang hàng có cấu trúc nói chung và Chord nói riêng, quan hệ hàng xóm của các nút được thiết lập mà không xem xét đến topo (topology) tầng dưới. Đó chính là nguyên nhân gây ra sự sai khác giữa topo của mạng DHT và topo mạng liên kết vật lý (topology mismatch). Điều này làm cho độ trễ truyền thông báo giữa các nút và chi phí truyền thông trong mạng P2P. Yêu cầu đặt ra là làm sao để tối ưu mạng phủ, khắc phục sự khác biệt đó.

Ngoài ra, khi xây dựng bảng định tuyến trong cấu trúc Chord, liên kết tại hàng thứ i được chọn cố định là nút quản lý định danh k+2i. Như vậy, quá trình xây dựng liên kết trong bảng định tuyến cũng không xem xét đến quan hệ giữa các nút ở tầng dưới. Nếu như liên kết này có thời gian trễ lớn thì tất cả những truy vấn đi qua nó đều bị ảnh hưởng bởi độ trễ này. Quá trình chuyển tiếp truy vấn là đưa truy vấn đến vị trí mà khóa cần tìm kiếm thuộc lân cận của vị trí đó. Vì thế, phương pháp hiện có để xây dựng các liên kết trong bảng định tuyến là chưa tốt.

Khóa luận này sẽ đề xuất một phương pháp mới để giải quyết hai vấn đề nêu trên xảy ra với mạng ngang hàng có cấu trúc nói chung và cấu trúc Chord nói riêng. Vẫn dựa trên cấu trúc và định tuyến của Chord truyền thống, trong đề xuất mà khóa luận đưa ra, thứ nhất, các nút tham gia vào mạng sẽ lựa chọn vị trí theo tiêu chí mà tại đó, nút được chọn có thời gian trễ tới các nút liền trước và liền sau là nhỏ nhất; thứ hai, bảng định tuyến của nút sẽ được thay đổi bằng cách lựa chọn lại các nút đích của các liên kết từ một tập nút nào đó cũng theo tiêu chí thời gian trễ nhỏ nhất, nhằm tiết kiệm chi phí đường đi của các thông báo. Hai đề xuất sẽ giải quyết lần lượt vấn đề khác biệt về topo và xây dựng liên kết trong bảng định tuyến dựa vào thời gian trễ.

Để đánh giá hiệu quả của giải pháp đề xuất, khóa luận xây dựng một chương trình mô phỏng giả lập mạng Internet và đo thời gian trễ truyền thông báo giữa các nút trong mạng Chord. Các kết quả thử nghiệm chứng minh cho khả năng của giải pháp đề xuất trong việc giảm thời gian truyển thông báo trên mạng, kéo theo giảm chi phí truyền thông.

Khóa luận được chia thành năm chương:

Chương 1: Giới thiệu tổng quan về ngạng ngang hàng, ưu nhược điểm và sự phân loại mạng ngang hàng; những kiến thức cơ bản về DHT và đặc biệt là cấu trúc Chord.

Chương 2: Đề cập đến sự tối ưu hóa trong mạng Chord, các vấn đề và các nghiên cứu cho những vấn đề đó.

Chương 3: Đề xuất giải pháp tối ưu cấu trúc Chord dựa trên độ trễ, những ưu nhược điểm của giải pháp đó.

Chương 4: Xây dựng chương trình mô phỏng, các bước thực thi chương trình và những đánh giá từ kết quả đạt được.

Chương 5: Kết luận, những vấn đề nảy sinh và hướng đi tiếp theo.