Luận Văn Thạc Sĩ Về Điều Khiển Tắc Nghẽn Trong Mạng Ngang Hàng Có Cấu Trúc

Luận văn thạc sĩ VNU UET nghiên cứu điều khiển tắc nghẽn trên mạng ngang hàng có cấu trúc, mang lại giải pháp tối ưu cho hiệu suất mạng.

• Người hướng dẫn: TS. Nguyễn Hoài Sơn
• Trường học: Đại Học Quốc Gia Hà Nội
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Điều Khiển Tắc Nghẽn Trong Mạng Ngang Hàng Có Cấu Trúc
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2011
• Địa điểm: Hà Nội

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHƯƠNG 1: MẠNG NGANG HÀNG
• 2. CHƯƠNG 2: VẤN ĐỀ ĐIỀU KHIỂN TẮC NGHẼN TRONG MẠNG NGANG HÀNG CÓ CẤU TRÚC
• 3. CHƯƠNG 3: CÁC NGHIÊN CỨU LIÊN QUAN
• 4. CHƯƠNG 4: ĐỀ XUẤT VÀ PHÂN TÍCH GIẢI PHÁP ĐIỀU KHIỂN TẮC NGHẼ DỰA TRÊN VIỆC THAY ĐỔI BẢNG ĐỊNH TUYẾN
• 5. CHƯƠNG 5: XÂY DỰNG CHƯƠNG TRÌNH MÔ PHỎNG VÀ CÁC KẾT QUẢ ĐÃ ĐẠT ĐƯỢC
• 6. CHƯƠNG 6: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• DANH MỤC HÌNH ẢNH

Tóm tắt

I. Tổng Quan Về Điều Khiển Tắc Nghẽn Trong Mạng Ngang Hàng

Mạng ngang hàng có cấu trúc đang trở thành một phần quan trọng trong công nghệ thông tin hiện đại. Việc điều khiển tắc nghẽn trong mạng này là một thách thức lớn. Tắc nghẽn có thể dẫn đến giảm hiệu suất và thậm chí sụp đổ mạng. Do đó, việc hiểu rõ về cơ chế điều khiển tắc nghẽn là rất cần thiết.

1.1. Định Nghĩa Mạng Ngang Hàng Có Cấu Trúc

Mạng ngang hàng có cấu trúc là một mô hình phân tán, nơi các nút chia sẻ tài nguyên mà không cần máy chủ trung tâm. Điều này giúp tăng cường khả năng mở rộng và giảm thiểu điểm lỗi đơn lẻ.

1.2. Tầm Quan Trọng Của Việc Điều Khiển Tắc Nghẽn

Điều khiển tắc nghẽn là yếu tố quyết định đến hiệu suất của mạng. Nếu không có cơ chế điều khiển hợp lý, tắc nghẽn có thể lan rộng và gây ra sự cố nghiêm trọng cho toàn bộ hệ thống.

II. Vấn Đề Tắc Nghẽn Trong Mạng Ngang Hàng Có Cấu Trúc

Tắc nghẽn trong mạng ngang hàng có cấu trúc thường xảy ra khi một số nút nhận quá nhiều truy vấn. Điều này dẫn đến tình trạng quá tải và giảm hiệu suất mạng. Phân tích nguyên nhân và hậu quả của tắc nghẽn là rất quan trọng.

2.1. Nguyên Nhân Gây Ra Tắc Nghẽn

Tắc nghẽn có thể do nhiều nguyên nhân, bao gồm số lượng truy vấn lớn đến một nút cụ thể hoặc sự không đồng đều trong khả năng xử lý của các nút trong mạng.

2.2. Hậu Quả Của Tình Trạng Tắc Nghẽn

Hậu quả của tắc nghẽn có thể bao gồm giảm tốc độ truyền tải dữ liệu, tăng độ trễ và thậm chí là sụp đổ mạng. Điều này ảnh hưởng nghiêm trọng đến trải nghiệm người dùng và hiệu suất hệ thống.

III. Phương Pháp Điều Khiển Tắc Nghẽn Hiệu Quả

Có nhiều phương pháp để điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc. Các phương pháp này giúp giảm thiểu tình trạng tắc nghẽn và cải thiện hiệu suất mạng. Việc lựa chọn phương pháp phù hợp là rất quan trọng.

3.1. Phương Pháp CSCC

Phương pháp CSCC (Congestion Control and Coordination) giúp theo dõi và điều chỉnh lưu lượng truy cập đến các nút, từ đó giảm thiểu tình trạng tắc nghẽn.

3.2. Phương Pháp BPCC

BPCC (Bandwidth Proportional Congestion Control) điều chỉnh băng thông dựa trên tỷ lệ truy cập của các nút, giúp cân bằng tải và giảm thiểu tắc nghẽn.

IV. Ứng Dụng Thực Tiễn Của Các Phương Pháp Điều Khiển Tắc Nghẽn

Các phương pháp điều khiển tắc nghẽn đã được áp dụng trong nhiều ứng dụng thực tiễn. Việc áp dụng đúng phương pháp có thể cải thiện đáng kể hiệu suất của mạng ngang hàng có cấu trúc.

4.1. Kết Quả Nghiên Cứu Về Tắc Nghẽn

Nghiên cứu cho thấy rằng việc áp dụng các phương pháp điều khiển tắc nghẽn đã giúp giảm thiểu tình trạng tắc nghẽn và cải thiện thông lượng mạng.

4.2. Ví Dụ Minh Họa Từ Các Hệ Thống Thực Tế

Nhiều hệ thống thực tế đã áp dụng thành công các phương pháp điều khiển tắc nghẽn, cho thấy hiệu quả rõ rệt trong việc duy trì hoạt động của mạng.

V. Kết Luận Về Điều Khiển Tắc Nghẽn Trong Mạng Ngang Hàng

Điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc là một lĩnh vực nghiên cứu quan trọng. Việc phát triển các phương pháp hiệu quả sẽ giúp cải thiện đáng kể hiệu suất mạng trong tương lai.

5.1. Tương Lai Của Nghiên Cứu Về Tắc Nghẽn

Nghiên cứu về điều khiển tắc nghẽn sẽ tiếp tục phát triển, với nhiều phương pháp mới được đề xuất để giải quyết các vấn đề hiện tại.

5.2. Khuyến Nghị Đối Với Các Nhà Nghiên Cứu

Các nhà nghiên cứu nên tập trung vào việc phát triển các giải pháp linh hoạt và hiệu quả hơn để điều khiển tắc nghẽn, nhằm đáp ứng nhu cầu ngày càng cao của người dùng.

Nội dung chính

Tổng quan nghiên cứu

Mạng ngang hàng có cấu trúc (Structured Peer-to-Peer - P2P) ngày càng trở nên phổ biến trong các hệ thống phân tán nhờ khả năng mở rộng và tính phân tán cao. Theo ước tính, các mạng ngang hàng có thể bao gồm hàng triệu nút với khả năng xử lý và băng thông đa dạng, tạo ra thách thức lớn trong việc duy trì hiệu năng và ổn định mạng. Một trong những vấn đề kỹ thuật quan trọng là tắc nghẽn cục bộ trên các nút, khi số lượng truy vấn vượt quá khả năng xử lý, dẫn đến hiện tượng sụp đổ mạng nếu không có cơ chế điều khiển tắc nghẽn hiệu quả. Mục tiêu nghiên cứu của luận văn là đề xuất một phương pháp điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc, cụ thể là mô hình mạng Chord, nhằm nâng cao thông lượng và độ ổn định của hệ thống. Nghiên cứu tập trung trong phạm vi mạng ngang hàng có cấu trúc sử dụng bảng băm phân tán (DHT) với số lượng nút lên đến khoảng một triệu, mô phỏng trên môi trường mạng giả lập đa miền với độ trễ khác nhau. Ý nghĩa của nghiên cứu được thể hiện qua việc cải thiện các chỉ số như tỷ lệ truy vấn thành công, giảm số lượng gói tin bị loại bỏ và tăng khả năng phục vụ của mạng trong điều kiện tải cao.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

• Mạng ngang hàng có cấu trúc (Structured P2P): Mạng phủ được tổ chức theo cấu trúc vòng tròn với các nút và khóa được ánh xạ bằng kỹ thuật consistent hashing, giúp phân phối tải đồng đều và định tuyến hiệu quả.
• Bảng băm phân tán (Distributed Hash Table - DHT): Cơ chế lưu trữ và truy xuất dữ liệu phân tán, đảm bảo khả năng mở rộng và chống lỗi trong mạng.
• Mô hình mạng Chord: Giao thức định tuyến dựa trên bảng finger, mỗi nút duy trì thông tin về O(log N) nút khác, cho phép tìm kiếm successor của khóa trong O(log N) bước.
• Khái niệm tắc nghẽn và điều khiển tắc nghẽn: Tắc nghẽn xảy ra khi tải truy vấn vượt quá khả năng xử lý của nút, gây ra hiện tượng sụp đổ mạng. Điều khiển tắc nghẽn nhằm cân bằng tải, giảm thiểu mất mát gói tin và duy trì hiệu năng mạng.
• Các phương pháp điều khiển tắc nghẽn hiện có: CSCC (Credit System Congestion Control), BPCC (Back-Pressure Congestion Control), Marking, và định tuyến thích nghi.

Phương pháp nghiên cứu

• Nguồn dữ liệu: Dữ liệu mô phỏng mạng Chord với số lượng nút lên đến 1000-1 triệu, sử dụng mô hình đa miền với độ trễ nội miền và liên miền được sinh ngẫu nhiên theo phân phối Poisson.
• Phương pháp phân tích: Xây dựng chương trình mô phỏng mạng Chord, cài đặt phương pháp điều khiển tắc nghẽn dựa trên thay đổi bảng định tuyến, so sánh với mô hình Chord chuẩn về các chỉ số như số lượng gói tin bị loại bỏ, số gói tin phát sinh thêm, và thông lượng đạt được.
• Timeline nghiên cứu: Nghiên cứu được thực hiện trong năm 2011, bao gồm các bước: tổng quan lý thuyết, phân tích vấn đề tắc nghẽn, khảo sát các phương pháp hiện có, đề xuất giải pháp mới, xây dựng mô phỏng và đánh giá kết quả.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Phân tích quá trình sụp đổ do tắc nghẽn: Với mạng DHT gồm khoảng 1 triệu nút, khi tốc độ truy vấn vượt quá giá trị tối ưu (xopt ≈ 11 truy vấn/giây trong trường hợp bottleneck uplink, và ≈ 10.9 truy vấn/giây trong trường hợp bottleneck xử lý), thông lượng đạt được giảm mạnh, dẫn đến sụp đổ mạng.
2. Hiệu quả của phương pháp điều khiển tắc nghẽn dựa trên thay đổi bảng định tuyến: Mô phỏng cho thấy phương pháp này giảm đáng kể số lượng truy vấn bị loại bỏ so với mô hình Chord chuẩn, đặc biệt khi tốc độ truy vấn tăng cao.
3. Ảnh hưởng của việc thay đổi bảng định tuyến: Việc thay thế nút tắc nghẽn bằng nút lân cận không làm tăng số lượng nút phải đi qua trong mỗi truy vấn, giữ nguyên hiệu năng định tuyến với số bước trung bình là O(log N).
4. So sánh với các phương pháp hiện có: Phương pháp Marking cho hiệu quả tốt hơn CSCC và BPCC về thông lượng và thời gian phản hồi, tuy nhiên phương pháp đề xuất trong luận văn có ưu điểm đơn giản, giảm thiểu thông tin phụ và dễ dàng tích hợp với các phương pháp điều chỉnh lưu lượng.

Thảo luận kết quả

Nguyên nhân chính của tắc nghẽn là sự không đồng đều về khả năng xử lý và băng thông giữa các nút, cùng với sự tập trung truy vấn vào một số nút nhất định. Việc thay đổi bảng định tuyến giúp phân tán lại lưu lượng truy vấn, tránh nút bị quá tải. So với các nghiên cứu trước, phương pháp này không yêu cầu tăng kích thước bảng định tuyến hay theo dõi trạng thái nhiều nút, giảm thiểu chi phí duy trì mạng. Kết quả mô phỏng được trình bày qua biểu đồ số lượng gói tin bị loại bỏ và số gói tin phát sinh thêm, minh họa rõ ràng sự cải thiện về hiệu năng. Tuy nhiên, phương pháp vẫn còn hạn chế khi các nút thay thế cũng bị tắc nghẽn hoặc khi tốc độ truy vấn vượt quá khả năng tổng thể của mạng, cần kết hợp với các cơ chế điều chỉnh lưu lượng để tránh sụp đổ mạng hoàn toàn.

Đề xuất và khuyến nghị

1. Triển khai cơ chế phát hiện tắc nghẽn mềm và cứng trên từng nút: Thiết lập hai ngưỡng softLimitRate và hardLimitRate để phát hiện sớm và xử lý kịp thời tắc nghẽn, giúp giảm thiểu mất mát gói tin. Chủ thể thực hiện: quản trị mạng, timeline: 3-6 tháng.
2. Thay đổi bảng định tuyến động khi phát hiện tắc nghẽn: Thay thế nút tắc nghẽn bằng nút lân cận không bị tắc nghẽn, ưu tiên nút có định danh xa hơn nút nguồn để giảm số bước truy vấn. Chủ thể thực hiện: nhà phát triển phần mềm mạng, timeline: 6-9 tháng.
3. Xây dựng cơ chế phục hồi bảng định tuyến khi nút hết tắc nghẽn: Gửi thông báo đến các nút đã thay đổi bảng định tuyến để khôi phục trạng thái ban đầu, đảm bảo tính ổn định và hiệu quả lâu dài. Chủ thể thực hiện: nhà phát triển phần mềm mạng, timeline: 3 tháng.
4. Kết hợp phương pháp thay đổi bảng định tuyến với các cơ chế điều chỉnh lưu lượng như Marking hoặc BPCC: Giúp kiểm soát tốc độ truy vấn, tránh tình trạng tắc nghẽn lan rộng và sụp đổ mạng. Chủ thể thực hiện: nhà nghiên cứu và phát triển, timeline: 12 tháng.
5. Tối ưu hóa tham số phát hiện tắc nghẽn (hằng số x trong softLimitRate): Điều chỉnh để cân bằng giữa độ nhạy và độ ổn định của hệ thống, tránh phát hiện sai hoặc xử lý muộn. Chủ thể thực hiện: quản trị mạng, timeline: 3 tháng.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và phát triển mạng phân tán: Nghiên cứu các giải pháp điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc, áp dụng vào các hệ thống phân tán quy mô lớn.
2. Kỹ sư phát triển phần mềm mạng P2P: Tích hợp và cải tiến các thuật toán định tuyến và điều khiển tắc nghẽn nhằm nâng cao hiệu năng và độ ổn định của ứng dụng.
3. Quản trị viên hệ thống mạng doanh nghiệp: Áp dụng các kiến thức về tắc nghẽn và điều khiển tắc nghẽn để tối ưu hóa mạng nội bộ hoặc mạng phân tán sử dụng công nghệ P2P.
4. Sinh viên và học viên cao học chuyên ngành Công nghệ Thông tin, Truyền dữ liệu và Mạng máy tính: Tham khảo để hiểu sâu về mô hình mạng Chord, kỹ thuật DHT và các phương pháp điều khiển tắc nghẽn trong mạng ngang hàng.

Câu hỏi thường gặp

1. Tại sao tắc nghẽn lại là vấn đề nghiêm trọng trong mạng ngang hàng có cấu trúc?
   Tắc nghẽn xảy ra khi số lượng truy vấn vượt quá khả năng xử lý của nút, gây ra mất mát gói tin và giảm hiệu năng mạng. Nếu không kiểm soát, tắc nghẽn có thể lan rộng và dẫn đến sụp đổ toàn mạng, làm gián đoạn dịch vụ.

2. Phương pháp điều khiển tắc nghẽn dựa trên thay đổi bảng định tuyến hoạt động như thế nào?
   Khi phát hiện nút tắc nghẽn, các nút gửi truy vấn sẽ thay đổi bảng định tuyến để chuyển hướng truy vấn qua các nút lân cận không bị tắc nghẽn, giảm tải cho nút quá tải mà không làm tăng số bước truy vấn.

3. Phương pháp này có ưu điểm gì so với các phương pháp điều chỉnh lưu lượng như CSCC hay BPCC?
   Phương pháp thay đổi bảng định tuyến đơn giản, giảm thiểu thông tin phụ và chi phí duy trì, không cần theo dõi trạng thái nhiều nút, đồng thời tránh việc drop gói tin hoặc chờ đợi lâu như CSCC và BPCC.

4. Làm thế nào để phát hiện tắc nghẽn trên một nút trong mạng?
   Sử dụng hai ngưỡng softLimitRate và hardLimitRate dựa trên tốc độ xử lý và băng thông của nút. Khi tải vượt softLimitRate, nút được coi là tắc nghẽn mềm và bắt đầu xử lý chống tắc nghẽn; vượt hardLimitRate thì tắc nghẽn hoàn toàn.

5. Phương pháp này có thể áp dụng cho các mạng ngang hàng khác ngoài Chord không?
   Có thể áp dụng cho các mạng ngang hàng có cấu trúc sử dụng bảng định tuyến tương tự DHT, tuy nhiên cần điều chỉnh phù hợp với đặc điểm định tuyến và cấu trúc mạng cụ thể.

Kết luận

• Mạng ngang hàng có cấu trúc, đặc biệt là mô hình Chord, dễ gặp phải vấn đề tắc nghẽn cục bộ gây sụp đổ mạng khi tải truy vấn vượt quá khả năng xử lý.
• Phân tích mô hình và mô phỏng cho thấy thông lượng mạng giảm mạnh khi vượt ngưỡng tải tối ưu, xác định rõ tầm quan trọng của cơ chế điều khiển tắc nghẽn.
• Phương pháp điều khiển tắc nghẽn dựa trên thay đổi bảng định tuyến được đề xuất giúp chuyển hướng truy vấn tránh nút tắc nghẽn, giữ nguyên số bước truy vấn và giảm thiểu chi phí duy trì.
• Kết quả mô phỏng chứng minh phương pháp giảm đáng kể số lượng truy vấn bị loại bỏ và tăng thông lượng mạng so với mô hình Chord chuẩn.
• Các bước tiếp theo bao gồm tối ưu tham số phát hiện tắc nghẽn, kết hợp với các cơ chế điều chỉnh lưu lượng và mở rộng áp dụng cho các mạng ngang hàng khác.

Call-to-action: Các nhà nghiên cứu và kỹ sư phát triển mạng ngang hàng nên áp dụng và tiếp tục cải tiến phương pháp điều khiển tắc nghẽn này để nâng cao hiệu năng và độ ổn định của các hệ thống phân tán quy mô lớn trong thực tế.

Trích đoạn nội dung tài liệu

Chương 1. Mạng ngang hàng Mạng ngang hàng được định nghĩa như sau: một cấu trúc mạng phân tán, nếu như các thành phần tham gia chia sẻ tài nguyên của chúng (như khả năng tính toán của vi xử lý, dung lượng lưu trữ, đường truyền…). Các tài nguyên được chia sẻ này dùng để cung cấp các dịch vụ và nội dung. Chúng được truy cập một các trực tiếp bởi các nút khác, không thông qua các nút trung gian.

Các thành phần tham gia trong mạng vừa đóng vai trò cung cấp tài nguyên và yêu cầu tài nguyên.[6] Ta có thể phân biệt mô hình mạng ngang hàng với mô hình khách chủ thông qua vai trò của các thành phần tham gia trong mạng. Mỗi thành phần trong mạng ngang hàng có thể được gọi là Servent được tạo nên từ hai phần: Serv trong từ server (máy chủ) và ent trong từ client (máy khách), nhằm thể hiện khả năng của một nút trong mạng ngang hàng có thể vừa đóng cả hai vai trò máy chủ và máy khách trong cùng một thời điểm. Điều này hoàn toàn khác biệt với môi hình khách chủ khi nút tham gia chỉ có thể đóng một trong hai vai trò, hoặc máy khách, hoặc máy chủ tại một thời điểm. Hoạt động của bất cứ hệ thống mạng ngang hàng nào cũng phụ thuộc vào mạng bao gồm các nút và kết nối giữa chúng.

Mạng này được tạo ở tầng trên và độc lập với mạng vật lý phía dưới (thường là mạng IP), nên được gọi là “mạng phủ”. Mô hình, cấu trúc, mức độ tập trung của mạng phủ, và cách thức định tuyến, định vị trong mạng ảnh hưởng lớn đến hoạt động của hệ thống, do chúng sẽ quyết định tới khả năng tự bảo trì, tự ổn định mạng, chống lỗi, hiệu năng, khả năng mở rộng và mức độ bảo mật. Mạng phủ có thể phân biệt dựa vào mức độ phân tán và cấu trúc [1] 1. Mức độ phân tán Mặc dù thiết kế mong muốn của mạng phủ là hoàn toàn phân tán, tuy nhiên trong thực tế có thể không đúng như vậy.

Dưới đây liệt kê các mô hình dựa trên mức độ phân tán của chúng Mô hình phân tán hoàn toàn: Tất cả các nút trong mạng thực hiện các vai trò như nhau. Vừa đóng vai trò là máy chủ, vừa là máy khách. Do đó không cần phải có bất kỳ thành phần nào đóng vai trò là trung tâm điều phối. LUAN VAN CHAT LUONG download : add [e-mail] 4 Hình 1: Mạng ngang hàng phân tán hoàn toàn Mô hình phân tán một phần: Về cơ bản mô hình này tương tự như mô hình phân tán hoàn toàn.

Tuy nhiên có một số nút đóng vai trò quan trong hơn các nút khác, trở thành các điểm điều phối cho một số các nút khác. Các nút này được gọi là siêu nút (supernode) và chúng có thể đảm nhận các vai trò khác nhau tùy thuộc vào từng thiết kế. Hình 2: Mạng ngang hàng phân tán một phần Có một điểm quan trọng cần lưu ý là hệ thống sẽ không lệ thuộc vào một nút nào, dù nút đó có là supernode, do các nút này được gán động và nếu có lỗi sẽ được thay thế bằng nút khác. LUAN VAN CHAT LUONG download : add [e-mail] 5 Mô hình phân tán lai: Trong những hệ thống này, tồn tại một máy chủ trung tâm đóng vai trò duy trì thông tin về các nút và tài nguyên trên các nút.

Hình 3: Mạng ngang hàng lai Mặc dù việc trao đổi tài nguyên có thể thực hiện trực tiếp giữa các nút, nhưng máy chủ trung tâm sẽ đóng vai trò tổng hợp và tìm kiếm tài nguyên trên nút. Về cơ bản mô hình này sẽ xuất hiện single point of failure chính là máy chủ trung tâm. Mô hình này sẽ khó mở rộng, và tạo các nguy hiểm tiềm tàng cho hệ thống khi máy chủ trung tâm có sự cố hoặc bị tấn công. Cấu trúc mạng Cấu trúc ở đây mang nghĩa xác định rõ việc hình thành mạng phủ, cũng như việc nút và các tài nguyên được đưa vào mạng có theo một quy luật nhất định nào đó không.

Nhờ đó ta phân loại ra như sau Không có cấu trúc: Vị trí của nội dung hoàn toàn không liên quan tới mô hình của mạng phủ. Trong mạng không có cấu trúc nội dung cần phải được định vị. Phương thức tìm kiếm rất đa dạng từ việc sử dụng các phương pháp bruteforce, đẩy truy vấn ra tất cả các nút cho tới khi có được kết quả, cho đến sử dụng các thuật toán phức tạp và tiết kiệm tài nguyên hơn truy vấn ngẫu nhiên (random walks) hay dùng bảng đinh tuyến. LUAN VAN CHAT LUONG download : add [e-mail] 6 Phương pháp tìm kiếm có liên hệ mật thiết và tác động sâu sắc tới tính ổn định, khả năng mở rộng và độ tin cậy của mạng.

Mạng không cấu trúc thương được sử dụng trong môi trường mà các nút trong mạng luôn thay đổi. Có cấu trúc: Mạng không cấu trúc gặp nhiều khó khăn khi mở rộng, để giải quyết vấn đề này mạng có cấu trúc được đưa ra. Trong mạng có cấu trúc, mô hình của mạng phủ được kiểm soát chặt chẽ, các tài nguyên trong mạng được đặt ở các vị trí xác định. Hệ thống đảm nhận trách nhiệm ánh xạ giữa tài nguyên và vị trí của nút chứa tài nguyên đó, dưới dạng bảng định tuyến phân tán.

Khi đó truy vấn có thể tới được nút chứa tài nguyên một cách hiệu quả. Mạng có cấu trúc cung cấp khả năng mở rộng cho việc tìm kiếm chính xác truy vấn (truy vấn với định danh chính xác). Nhược điểm của mạng có cấu trúc là việc duy trì mạng sẽ gặp khó khăn khi có quá nhiều nút ra vào mạng. Mạng ngang hàng có cấu trúc Mạng không cấu trúc với sự phân bố tự do của nút và tài nguyên sẽ tồn tại nhược điểm về phương thức tìm kiếm gây tốn kém tài nguyên, đồng thời không đảm bảo sẽ luôn tìm được kết quả cho mỗi truy vấn.

Vấn đề này càng trở nên khó giải quyết khi số lượng nút trong mạng tăng. Lý do đó khiến mạng không cấu trúc không được áp dụng trong các hệ thống yêu cầu khả năng mở rộng cao. Để khắc phục nhược điểm này ta sử dụng mạng có cấu trúc với kĩ thuật bảng băm phân tán (DHT). [9] Bảng băm phân tán là một hệ thống phân tán cung cấp chức năng tìm kiếm tương tự như bảng băm thông thường.

Một cặp khóa và giá trị được lưu trong DHT và bất cứ nút nào tham gia vào hệ thống cũng có thể lấy được giá trị ứng với một khóa xác định. Việc duy trì bảng ánh xạ giữa khóa và các giá trị được lưu phân tán trên các nút, do đó việc thay đổi của một số nút tham gia vào hệ thống sẽ chỉ ảnh hưởng đến một số nhỏ các khóa liên quan. Điều này giúp cho DHT có thể dễ dàng mở rộng với số lượng lớn nút tham gia, và cung cấp khả năng duy trì hệ thống khi có nút tham gia, rời khỏi mạng, hay bị lỗi. LUAN VAN CHAT LUONG download : add [e-mail] 7 Hình 4: Bảng băm phân tán – DHT 1.

Đặc điểm của DHT Các đặc điểm của DHT có thể tóm tắt như sau:  Phân tán: DHT là tập hợp các nút mà không cần bất kì một máy trung tâm nào.  Chống lỗi: hệ thống hoạt động được trong trường hợp các nút liên tục ra, vào, hoặc bị lỗi  Khả năng mở rộng: hệ thống hoạt động ổn định khi có số lượng lớn các nút tham gia. Để đạt được các đặc điểm mô tả ở trên kỹ thuật được sử dụng chủ yếu là mỗi nút phải có liên hệ, trao đổi với một số nút khác có trong mạng – thông thường là O(log n) với mạng có n nút tham gia. Do đó chỉ cần một số ít điều chỉnh khi có sự thay đổi về các nút tham gia mạng.

Ngoài ra một hệ thống DHT cũng như bất kỳ hệ thống phân tán khác còn cần phải quan tâm đến các vấn đề như chống tấn công từ bên trong hay ngoài hệ thống, cân bằng tải, xác thực dữ liệu và hiệu năng của hệ thống 1. Cấu trúc hệ thống Cấu trúc của hệ thống DHT có thể gồm nhiều thành phần chính: Phần quan trọng nhất là không gian khóa ảo, ví dụ như chuỗi có độ dài 160 bit. Cách thức phân vùng của không gian khóa chia không gian khóa cho từng nút trong hệ thống. Một mạng phủ kết nối các nút với nhau, giúp các nút này tìm được nút đang giữ thông tin về một khóa trong không gian khóa.

Với các thành phần như trên DHT có thể sử dụng phương thức sau để lưu trữ và lấy dữ liệu. Giả sử có không gian khóa gồm các khóa có độ dài 160 bit. Để lưu một filie với tên file và dữ liệu của nó trong DHT, thuật toán SHA-1 được sử dụng để tạo mã băm của tên file – là khóa k có độ dài 160 bit. Tiếp đó một thông LUAN VAN CHAT LUONG download : add [e-mail] 8 báo put(k,data) được gửi đến các nút trong mạng DHT.

Thông điệp này được chuyển tiếp qua các nút qua mạng phủ cho đến khi tới được nút giữ trách nhiệm lưu giữ khóa k được quy định bởi cách phân bổ không gian khóa. Nút đó sẽ thực hiện lưu giữ khóa và dữ liệu. Các nút khác có thể lấy thông tin của file bằng cách thực hiện hàm băm trên tên file để lấy được khóa k, sau đó truy vấn bất kỳ nút nào trong mạng DHT để tìm kiếm dữ liệu ứng với khóa k bằng thông điệp get(k). Thông điệp này tương tự được truyền trên mạng phủ thông qua các nút cho đến khi tới nút lưu giữ thông tin về khóa k, nút này sẽ trả lại thông tin về dữ liệu ứng với khóa.

Cách thức phân bổ không gian khóa và các thành phần của mạng phủ của một hệ thống DHT cơ bản sẽ được mô tả như ở dưới Phân bổ không gian khóa Phần lớn các hệ thống DHT sử dụng các phương pháp consistent hashing để ánh xạ khóa vào các nút. Kĩ thuật này cung cấp một hàm δ(k1,k2) để tính khoảng cách giữa hai khóa k1 và k2. Khoảng cách này không liên quan gì đến khoảng cách vật lý hay độ trễ của mạng. Mỗi nút được gán cho một khóa định danh ID.

Một nút với ID là ix sẽ có trách nhiệm lưu trữ với tất cả các khóa km nếu như ix là định danh nút gần nhất với các khóa đó, tính toán bằng hàm δ(k1,k2).