Luận văn thạc sĩ: Giải pháp cân bằng tải cho mạng ngang hàng có cấu trúc

Luận văn thạc sĩ: Giải pháp cân bằng tải dùng cấu trúc thư mục cho mạng ngang hàng có cấu trúc. Mã số: 60 48 15002. Tìm hiểu ngay!

• Tác giả: Đỗ Cao Minh
• Người hướng dẫn: TS. Nguyễn Hoài Sơn
• Trường học: Trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Giải Pháp Cân Bằng Tải Sử Dụng Cấu Trúc Thư Mục Cho 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: 2010
• Địa điểm: Hà Nội

Mục lục chi tiết

• MỤC LỤC
• DANH MỤC THUẬT NGỮ
• DANH MỤC HÌNH VẼ
• 1. CHƢƠNG 1 - TỔNG QUAN VỀ MẠNG NGANG HÀNG
• 1.1. Tổng quan về mạng ngang hàng
• 1.1.1. Khái niệm về mạng ngang hàng
• 1.1.2. Ưu điểm của mạng ngang hàng
• 1.1.3. Nhược điểm của mạng ngang hàng
• 1.2. Phân loại mạng ngang hàng
• 1.2.1. Phân loại theo mức độ tập trung của các node mạng
• 1.2.2. Phân loại theo cấu trúc liên kết
• 1.3. Mạng ngang hàng có cấu trúc dựa trên DHT(Distributed Hash Table)
• 1.3.1. Giới thiệu DHT
• 2. CHƢƠNG 2 - CÂN BẰNG TẢI TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC
• 2.1. Khái niệm về tải trên mạng ngang hàng
• 2.1.1. Node quá tải
• 2.1.2. Node có tải cao và Node có tải thấp
• 2.2. Các nguyên nhân dẫn đến mất cân bằng tải trên các hệ thống DHT
• 2.2.1. Định danh các node không cân bằng
• 2.2.2. Định danh dữ liệu không cân bằng
• 2.2.3. Khả năng các node không cân bằng
• 2.3. Các giải pháp cân bằng tải
• 2.3.1. Hướng sử dụng server ảo
• 2.3.2. Hướng không sử dụng server ảo
• 3. CHƢƠNG 3 - ĐỀ XUẤT CẢI TIẾN THUẬT TOÁN CÂN BẰNG TẢI THEO NGƢỠNG
• 3.1. Một số khái niệm
• 3.2. Thuật toán ThresholdPlus
• 4. CHƢƠNG 4 - ĐÁNH GIÁ HIỆU QUẢ CỦA GIẢI PHÁP ĐỀ XUẤT DỰA TRÊN MÔ PHỎNG
• 4.1. Ảnh hƣởng thời gian sống của một node tới các thuật toán cân bằng tải
• 4.2. Ảnh hƣởng của số lƣợng các câu truy vấn tới các thuật toán cân bằng tải
• 4.3. Ảnh hƣởng của câu truy vấn dạng Zipf tới các thuật toán cân bằng tải
• 4.4. So sánh kết quả thực nghiệm của thuật toán Threshol Plus với các thuật toán đã có:
• 5. CHƢƠNG 5 - KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN
• 5.1. Hƣớng phát triển tiếp theo
• MỞ ĐẦU

Tóm tắt

I. Tổng Quan Về Cân Bằng Tải P2P Cấu Trúc Thư Mục

Mạng ngang hàng (P2P) đã phát triển mạnh mẽ trên Internet, tận dụng khả năng tính toán và băng thông của các máy tham gia thay vì tập trung vào máy chủ trung tâm. Sự phát triển này thúc đẩy sự ra đời của nhiều ứng dụng như chia sẻ file, tìm kiếm thông tin và tính toán lưới. Mạng ngang hàng có cấu trúc đảm bảo tính hiệu quả và khả năng mở rộng, nhưng vấn đề cân bằng tải P2P cần được giải quyết để đảm bảo chất lượng dịch vụ. Luận văn thạc sĩ này tập trung vào giải pháp cân bằng tải P2P cấu trúc thư mục, đặc biệt là hướng tiếp cận không dựa trên server ảo, và đề xuất một thuật toán cải tiến của thuật toán cân bằng tải theo ngưỡng. Thuật toán đề xuất cho phép các node quá tải tìm kiếm node phù hợp để thực hiện cân bằng tải một cách chính xác và nhanh chóng. Nghiên cứu đã cài đặt và thử nghiệm thuật toán trong điều kiện mạng gần với thực tế, cho thấy khả năng giải quyết tốt vấn đề cân bằng tải. Theo tài liệu gốc, có hai hướng tiếp cận chính cho các thuật toán cân bằng tải: dựa trên server ảo và không dựa trên server ảo. Luận văn này tập trung vào hướng thứ hai, đề xuất giải pháp cân bằng tải sử dụng cấu trúc thư mục. Cấu trúc thư mục được đề xuất giúp cải thiện hiệu quả tìm kiếm và giảm độ trễ.

1.1. Khái niệm cơ bản về mạng ngang hàng P2P

Mạng ngang hàng là mạng mà kiến trúc được tạo nên bởi các máy tính liên kết với nhau, các máy tính tham gia đều bình đẳng và được gọi là peer. Mỗi máy tính tham gia là một phần và duy trì sự tồn tại của mạng. Ứng dụng thường gặp nhất của mạng ngang hàng là chia sẻ file (âm thanh, hình ảnh, dữ liệu) hoặc để truyền dữ liệu thời gian thực. Việc sử dụng mạng ngang hàng mang lại nhiều ưu điểm cho người dùng, đặc biệt là khả năng tận dụng tài nguyên phân tán. Theo tài liệu gốc, mục đích quan trọng của mạng ngang hàng là các máy tính tham gia mạng đều đóng góp tài nguyên, bao gồm băng thông, lưu trữ và khả năng tính toán.

1.2. Ưu điểm và nhược điểm của kiến trúc P2P

Ưu điểm chính của mạng P2P là khả năng mở rộng và tính phi tập trung. Khi càng nhiều máy tính tham gia mạng, khả năng tổng thể của mạng càng lớn. Mô hình này phù hợp với tính phi tập trung của Internet, giúp cải thiện hiệu quả của các phương pháp phân tích và xử lý dữ liệu. Tính chất phân tán cũng giúp phân tán trách nhiệm cung cấp dịch vụ đến tất cả các node trên mạng, loại bỏ vấn đề ngừng trệ dịch vụ do một điểm cung cấp duy nhất gặp sự cố. Tuy nhiên, mạng P2P cũng có nhược điểm, bao gồm việc khó kiểm soát chất lượng dịch vụ và bảo mật, cũng như khả năng bị ngắt kết nối do các node có thể rời mạng bất kỳ lúc nào.

1.3. Tổng quan về Distributed Hash Table DHT

Distributed Hash Table (DHT) là hệ thống mạng phân tán cung cấp các dịch vụ tìm kiếm dựa vào bảng băm. Bảng băm là một cặp (tên, giá trị). Mỗi node tham gia mạng có thể dễ dàng tìm thấy giá trị mong muốn dựa vào tên của giá trị đó. Việc hình thành tên (khóa) và gắn các khóa đó với giá trị tương ứng được thực hiện trực tiếp tại các node trong mạng, giảm thiểu khả năng sập mạng khi các node tham gia hoặc dời bỏ mạng. DHT nhấn mạnh vào các thuộc tính: không tập trung, khả năng mở rộng và khả năng chịu lỗi. Một số mạng DHT nổi tiếng như Bittorrent, eDonkey network, Yacy….

II. Vấn Đề Cân Bằng Tải Trong Mạng P2P Cấu Trúc DHT

Trong mạng P2P dựa trên DHT, cân bằng tải là yếu tố quan trọng để đảm bảo hiệu suất và tính sẵn sàng của hệ thống. Tuy nhiên, có nhiều nguyên nhân dẫn đến mất cân bằng tải, bao gồm việc phân bố dữ liệu không đồng đều, sự khác biệt về khả năng của các node, và sự xuất hiện của các "hot spot" - các file hoặc tài nguyên được truy cập nhiều hơn các file khác. Luận văn này phân tích các nguyên nhân này và đề xuất giải pháp để giảm thiểu tình trạng mất cân bằng tải. Một số nguyên nhân chính dẫn đến mất cân bằng tải bao gồm định danh các node không cân bằng, định danh dữ liệu không cân bằng, hot spots và khả năng các node không cân bằng. Theo tài liệu gốc, kết quả mô phỏng hệ thống DHT Chord với 4,096 node và khoảng 500,000 files dữ liệu cho thấy không có sự phân bố tối ưu dữ liệu trên các node.

2.1. Nguyên nhân gây mất cân bằng tải trên DHT

Mất cân bằng tải có thể do định danh được chọn ngẫu nhiên, dẫn đến mỗi node quản lý một vùng với số lượng file dữ liệu được gán khác nhau. Sự khác biệt về kích cỡ của vùng nhỏ nhất và lớn nhất có thể lên tới O(NlogN). Ngoài ra, nếu dữ liệu được phân bố quá tập trung vào một vùng, cũng sẽ gây tình trạng "nặng tải" tại khu vực đó. Các node Hot spot cũng là một nguyên nhân khi một số file được truy vấn nhiều hơn, dẫn đến việc truy cập vào nút này nhiều hơn, do đó nó phải chịu tải nhiều hơn các node bình thường khác. Cuối cùng, các node tham gia mạng thường rất đa dạng và có khả năng khác nhau, có những node là máy tính đời cũ kết nối Internet chậm, nhưng cũng có những máy có cấu hình mạnh kết nối internet băng thông rộng.

2.2. Ảnh hưởng của Hotspots tới hiệu năng mạng P2P

Hotspots gây ra sự tập trung truy cập vào một số ít node, làm tăng tải cho các node này và giảm hiệu năng của hệ thống. Việc xử lý các hot spot đòi hỏi các giải pháp đặc biệt, như replication (sao chép dữ liệu) hoặc caching (lưu trữ tạm thời dữ liệu) để giảm tải cho các node bị quá tải. Theo các nghiên cứu, trong các hệ thống P2P hiện nay chỉ có 10% số các file được truy vấn nhiều nhất và chiếm tới 60% tổng lưu thông trên mạng.

2.3. Tác động của khả năng khác nhau giữa các node

Các nút tham gia vào mạng thường rất đa dạng và có khả năng (CPU, Storage, Bandwidth) là khác nhau. Saroui và đồng nghiệp đã nghiên cứu 2 hệ thống chia sẻ files nổi tiếng là Napster và Gnutella cho thấy mức độ chênh lệch về khả năng của các node có thể lên tới 3, thậm chí là 5 lần. Trong một thực tế như vậy, nếu các vùng mà được gán cho các node yếu thì cho dù phân bố lưu trữ các files dữ liệu và truy vấn trong hệ thống đạt được sự đồng đều thì vẫn xảy ra sự mất cân bằng tải nghiêm trọng.

III. Các Giải Pháp Cân Bằng Tải P2P Hiện Nay Phân Tích

Hiện nay, có nhiều giải pháp cân bằng tải cho mạng P2P dựa trên DHT. Các giải pháp này được chia thành hai hướng chính: sử dụng server ảo và không sử dụng server ảo. Hướng tiếp cận dựa trên server ảo cho phép mỗi node vật lý quản lý một hoặc nhiều server ảo với các định danh ngẫu nhiên được chọn từ không gian định danh. Các server ảo hoạt động như các node tham gia mạng DHT. Hướng tiếp cận không sử dụng server ảo yêu cầu dịch chuyển định danh của các node trong hệ thống khi có một node tham gia hoặc rời khỏi hệ thống. Luận văn này trình bày và đánh giá các giải pháp cân bằng tải theo hai hướng tiếp cận trên. Theo tài liệu gốc, đã có nhiều nghiên cứu về cân bằng tải được các tác giả đưa ra cho hệ thống mạng P2P dựa trên DHT. Nói chung, các giải pháp này được phân thành hai hướng chính: hướng tiếp cận dựa trên server ảo (virtual server) và hướng tiếp cận không dựa trên server ảo.

3.1. Cân bằng tải P2P bằng phương pháp Server ảo

Theo hướng này, mỗi node vật lý quản lý một hoặc nhiều server ảo với các định danh ngẫu nhiên được chọn từ không gian định danh. Các server ảo hoạt động như các node tham gia mạng DHT. Trong một hệ thống với các node có khả năng đồng đều cao, mỗi node vật lý cần duy trì O(logn) server ảo để làm giảm nhân tố mất cân bằng xuống đến một hằng số. Với một hệ thống DHT gồm nhiều node có khả năng chịu tải khác nhau, mỗi node vật lý sẽ chọn một số lượng server ảo tỷ lệ với khả năng của nó.

3.2. Ưu điểm và nhược điểm của Server ảo

Ưu điểm của giải pháp này là tính linh hoạt và khả năng thích ứng với sự thay đổi trong hệ thống. Tuy nhiên, nó cũng có nhược điểm, bao gồm việc tăng chi phí quản lý và bảo trì, cũng như khả năng làm giảm hiệu suất của hệ thống nếu số lượng server ảo quá lớn. Giải pháp sử dụng server ảo còn tồn tại một số yếu điểm, chẳng hạn như để quản lý được các server ảo thì mỗi node phải duy trì khá nhiều liên kết đến các server ảo đó, thông thường số liên kết này là O(logn).

3.3. Cân bằng tải P2P bằng phương pháp không dùng Server ảo

Theo hướng này, mỗi định danh trong không gian địa chỉ sẽ tương ứng với một node vật lý trong mạng. Để đạt được sự cân bằng trong hệ thống, các giải pháp đưa ra đều phải dịch chuyển định danh của các node trong hệ thống khi có một node tham gia hoặc rời khỏi hệ thống. Một thuật toán điển hình đi theo hướng này đó là cân bằng tải theo ngưỡng.

IV. Đề Xuất Thuật Toán Cân Bằng Tải P2P Cải Tiến ThresholdPlus

Luận văn đề xuất thuật toán cân bằng tải P2P cải tiến, gọi là ThresholdPlus, dựa trên thuật toán cân bằng tải theo ngưỡng. Thuật toán này giảm số lượng thông báo phát ra để tìm kiếm một node nhẹ tải và có phương pháp chọn node nhẹ tải thỏa mãn điều kiện dịch chuyển một cách hiệu quả hơn. Giải pháp đề xuất có 2 điểm khác biệt so với các thuật toán đã có : Thứ nhất là nghiên cứu thuật toán cân bằng tải theo ngưỡng và khái niệm Directory được sử dụng trong các thuật toán cân bằng tải có sử dụng server ảo từ đó đề xuất một thuật toán cân bằng tải mới hoạt động hiệu quả hơn trong các hệ thống dựa trên DHT. Thứ hai là Thuật toán mới có xem xét đến cả tải xử lý các câu truy vấn tìm kiếm một node trong quá trình thực hiện cân bằng tải.

4.1. Ý tưởng chính của thuật toán ThresholdPlus

Thuật toán ThresholdPlus của chúng tôi nghiên cứu và đề xuất trên cơ sở của thuật toán Threshold được cải tiến ở cách thức tìm kiếm node nhẹ tải phù hợp và hiệu quả. Thuật toán của này được mô tả chi tiết, gồm ba bước: Node nhẹ tải thông báo cho các thư mục, Chia sẻ tải cho các node láng giềng và Định danh lại một node

4.2. Chi tiết các bước thực hiện của ThresholdPlus

Bước 1: Node nhẹ tải thông báo cho các thư mục: Định kỳ trong khoảng thời gian nhất định, các node sẽ chạy thuật toán kiểm tra tải của mình. Nếu một node có định danh L kiểm tra thấy mình là nhẹ tải, nó sẽ gửi một thông điệp tới hỏi successor của mình xem nếu khi chuyển sang định danh khác có làm cho node successor hoặc predecessor quá tải hay không?. Nếu không làm quá tải cho các node này thì node L có thể di chuyển được, khi đó node L sẽ gửi thông báo chứa thông tin của nó cho node phụ trách thư mục i, trong đó i = h(L), h là hàm băm ánh xạ định danh của node L vào một giá trị trong khoảng [0,d). Bước 2: Chia sẻ tải cho các node láng giềng: Đầu tiên node quá tải n sẽ kiểm tra xem hai node láng giềng của mình là (predecessor của n và successor của n) có khả năng nhận tải được hộ được hay không. Nếu được node n sẽ kiểm tra xem một trong hai láng riềng, láng riềng nào có tải thấp hơn nó sẽ thực hiện chia của mình cho node đó. Bước 3: Định danh lại một node: node n sẽ chọn ngẫu nhiên một thư mục(Directory) i và gửi một thông điệp tới node phụ trách thư mục đó để tìm kiếm một node nhẹ tải. Thư mục i sẽ xem xét vào yêu cầu giảm tải (chia tải) của node nặng tải và khả năng của các node nhẹ tải có trong thư mục để chọn ra một node nhẹ tải thích hợp nhất gửi cho node n.

4.3. Ưu điểm nổi bật của ThresholdPlus so với thuật toán cũ

Thuật toán ThresholdPlus có hai điểm khác biệt so với các thuật toán trước đó: Thứ nhất, để một node nặng tải tìm một node nhẹ tải thì node nặng tải phải đòi hỏi nhiều nhất (N-1) node để tìm thấy một node nhẹ tải. Giải pháp chúng tôi sử dụng thư mục để chứa các node nhẹ tải có thể dịch chuyển được nên đảm bảo chắc chắn rằng khi trong hệ thống còn có một node nhẹ tải thì node thực hiện quá trình cân bằng tải bao giờ cũng tìm được node nhẹ tải đó một cách nhanh chóng. Thứ hai, thư mục trong thuật toán ThresholdPlus chỉ chứa các node nhẹ tải có thể di chuyển được do đó số lượng node nhẹ tải trong thư mục quản lý ít hơn nhiều so với số server ảo nhẹ tải trong các thuật toán cân bằng tải dịch chuyển server ảo có sự dụng khái niệm thư mục. Các node nhẹ tải trong hệ thống trước khi gửi thông tin của mình cho Directory nó sẽ hỏi Successor của nó trước xem nếu nó di chuyển đi chỗ khác thì Successor có bị quá tải không. Nếu nó bị quá tải thì Node nhẹ tải đó sẽ không gửi thông tin cho Directory.

V. Đánh Giá Hiệu Quả Kết Quả Mô Phỏng Thuật Toán P2P

Phần này mô tả kết quả từ các thí nghiệm được cài đặt với thuật toán ThresholdPlus và so sánh với thuật toán Threshold và một số thuật toán khác đã đề cập trong luận văn. Trong thí nghiệm mô phỏng này, chúng tôi lựa chọn 10 thư mục và lưu trữ ở 10 node ngẫu nhiên trong mạng gồm 4096 node vật lý. Thí nghiệm đầu tiền mà chúng tôi thực hiện là xem xét khả năng thích ứng của các thuật toán cân bằng tải khi thời gian sống trung bình của một node biến. Kết quả của thí nghiệm cho thấy với số truy vấn trung bình 10 truy vấn/node, thuật toán ThresholdPlus có tỷ lệ thành công lớn hơn thuật toán Threshold khoảng 9% đối với truy vấn dạng Uniform và khoảng 14% đối với truy vấn dạng Zipf.

5.1. Thiết lập mô phỏng và các tham số sử dụng

Mô phỏng hoạt động theo thời gian rời rạc và sử dụng các tham số đầu vào. Mỗi bước thời gian gồm ba kịch bản: node tham gia và rời hệ thống, cập nhật bảng tìm đường, truy vấn dữ liệu và thực hiện cân bằng tải. Node vào và ra hệ thống tuân theo phân bố xác suất Pareto. Tại mỗi bước các node vào và ra hệ thống tuân theo phân bố xác suất Pareto.

5.2. So sánh hiệu năng của ThresholdPlus và Threshold

Với số truy vấn trung bình 10 truy vấn/node, thuật toán ThresholdPlus có tỷ lệ thành công lớn hơn thuật toán Threshold khoảng 9% đối với truy vấn dạng Uniform và khoảng 14% đối với truy vấn dạng Zipf. Thí nghiệm thứ hai mà luận văn kiểm tra xem các thuật toán cân bằng tải làm việc như thế nào khi số câu truy vấn phát ra từ các node tăng lên trong hệ thống.

5.3. Ảnh hưởng của thời gian sống trung bình của node

Thí nghiệm đầu tiền mà chúng tôi thực hiện là xem xét khả năng thích ứng của các thuật toán cân bằng tải khi thời gian sống trung bình của một node biến. Chúng tôi tạo ra các file theo rõi sự ra, vào của các node trong mạng với thời gian sống trung bình của các node được xét là 15 phút, 30 phút, 1 giờ, 2 giờ và 4 giờ.

VI. Kết Luận và Hướng Phát Triển Tương Lai Cho P2P

Luận văn này đã trình bày một giải pháp cân bằng tải P2P cấu trúc thư mục cải tiến, ThresholdPlus, và chứng minh hiệu quả của nó thông qua mô phỏng. Thuật toán này giảm số lượng thông báo cần thiết để tìm kiếm node nhẹ tải và có phương pháp chọn node nhẹ tải hiệu quả hơn. Hướng phát triển tiếp theo của nghiên cứu này có thể tập trung vào việc tối ưu hóa các tham số của thuật toán, cũng như đánh giá hiệu quả của nó trong các môi trường mạng thực tế. Ngoài ra, có thể nghiên cứu các giải pháp để giảm tải cho các node được chọn làm thư mục. Các thuật toán cân bằng tải theo ngưỡng hoạt động hiệu quả khi trong mạng có tỷ lệ số node nặng tải so với số node nhẹ tải là thấp. Trong trường hợp này node nặng tải thường chuyển tải ngay cho các node láng riềng, do đó tải truy vấn để tìm node nhẹ tải giảm đáng kể. Ngược lại, khi tỷ lệ trên cao, các node trong mạng hầu hết đều quá tải, khả năng chuyển tải của node quá tải cho láng riềng hầu như không xảy ra, chính vì vậy tải truy vấn đề tìm node nhẹ tải tăng rất nhanh.

6.1. Tóm tắt những đóng góp chính của luận văn

Luận văn đã đề xuất và đánh giá một thuật toán cân bằng tải P2P cải tiến, ThresholdPlus, dựa trên thuật toán cân bằng tải theo ngưỡng. Thuật toán này giảm số lượng thông báo cần thiết để tìm kiếm node nhẹ tải và có phương pháp chọn node nhẹ tải hiệu quả hơn.

6.2. Các hạn chế và vấn đề còn tồn tại

Những ưu điểm được kể ra ở trên giải pháp của chúng tôi cũng còn những nhược điểm sau: Làm tăng tải cho node được chọn làm thư mục. Phải xử lý việc mất mát dữ liệu khi có một node thư mục rời hệ thống.

6.3. Hướng nghiên cứu và phát triển trong tương lai

Hướng phát triển tiếp theo của nghiên cứu này có thể tập trung vào việc tối ưu hóa các tham số của thuật toán, cũng như đánh giá hiệu quả của nó trong các môi trường mạng thực tế. Ngoài ra, có thể nghiên cứu các giải pháp để giảm tải cho các node được chọn làm thư mục, cũng như cải thiện khả năng chịu lỗi của hệ thống.

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

Chương 1: Giới thiệu tổng quan về mạng ngang hàng, những khái niệm cơ bản về mạng ngang hàng đồng thời giới thiệu giao thức Chord, giao thức được sử dụng để triển khai mạng phủ DHT khi xây dựng chương trình mô phỏng. Chương 2: Tìm hiểu về vấn đề cân bằng tải trên mạng ngang hàng, một số nguyên nhân dẫn đến mất cân bằng tải, các giải pháp đã được đề xuất và phân tích về các giải pháp này. Chương 3: Trên cơ sở các vấn đề tìm hiểu được ở chương 2. Chúng tôi đề xuất giải pháp cân bằng trên mạng ngang hàng có cấu trúc theo hướng không sử dụng server ảo.

Đó là một giải thuật cải tiến của giải thuật cân bằng tải theo ngưỡng. TIEU LUAN MOI download : [e-mail] 7 Chương 4: Trình bày cách thực hiện chương trình mô phỏng đồng thời trình bày kết quả đánh giá giải thuật cân bằng tải dựa trên mô phỏng của chúng tôi. Chương 5: Trình bày các công việc mà chúng tôi đã thực hiện được, những vấn đề còn tồn tại của luận văn và hướng phát triển tiếp theo của chúng tôi. TIEU LUAN MOI download : [e-mail] 8 CHƢƠNG 1 - TỔNG QUAN VỀ MẠNG NGANG HÀNG Trong chương này, luận văn sẽ giới thiệu khái quát về mạng ngang hàng, các đặc điểm, các hình thức phân loại của mạng ngang hàng, khái niệm về DHT và mạng hàng có cấu trúc đồng thời giới thiệu về một số mạng ngang hàng đã và đang được ứng dụng có hiệu quả.1 Tổng quan về mạng ngang hàng 1.1 Khái niệm về mạng ngang hàng Mạng ngang hàng là một mạng mà kiến trúc của nó được tạo nên bởi các máy tính liên kết với nhau, các máy tính tham gia trong mạng đều bình đẳng như nhau và được gọi là các peer, mỗi máy tính tham gia mạng là một phần và duy trì sự tồn tại của mạng.

Các máy tính trong mạng thường xuyên liên lạc với các máy tính khác để ổn định mạng và chia sẻ dữ liệu với nhau. Dữ liệu được chứa trên các máy tính và được chia sẻ trực tiếp với nhau giữa các máy tính tham gia vào mạng. Mô hình mạng ngang hàng Ứng dụng thường xuyên gặp nhất của mạng ngang hàng là chia sẻ tệp tin, tất cả các dạng như: âm thanh, hình ảnh, dữ liệu. hoặc để truyền dữ liệu thời gian thực….

Việc sử dụng mạng ngang hàng mang lại nhiều ưu điểm cho người dùng. Luận văn xin trình bày một số ưu điểm của mạng ngang hàng. TIEU LUAN MOI download : skknchat@gmail.2 Ƣu điểm của mạng ngang hàng Mục đích quan trọng của mạng ngang hàng là các máy tính tham gia mạng đều đóng góp tài nguyên bao gồm băng thông, lưu trữ, khả năng tính toán. Do đó khi càng nhiều mày tính tham gia mạng thì khả năng tổng thể của mạng càng lớn.

Do việc các thông tin lưu trữ không chỉ trên máy chủ mà còn được lưu trữ ở chính các máy tham gia mạng nên mô hình này rất phù hợp với tính phi tập trung của Internet. Xét về khía cạnh sức mạnh xử lý, mạng ngang hàng có khả năng xử lý cao hơn cả những máy chủ lớn hiện nay, do đó sử dụng mạng ngang hàng có thể cải thiện đáng kể hiệu quả của các phương pháp phân tích, xử lý dữ liệu và giải các bài toán phức tạp. Sở dĩ làm được như vậy là vì mạng ngang hàng có thể tận dụng được khả năng xử lý, khả năng lưu trữ còn thừa của các máy tham gia mạng với những thuật toán phân tán hợp lý. Công nghệ này đã chia việc xử lý lớn ra thành nhiều việc xử lý để có thể giao cho các máy tính khác trong mạng cùng thực hiện.

Mỗi máy tính sẽ xử lý một phần công việc và trả về kết quả xử lý cho máy tính trung tâm, máy tính trung tâm sẽ ghép nối các kết quả này lại với nhau. Bằng cách như vậy, ta có thể giải quyết các bài toán phức tạp yêu cầu vấn đề xử lý, lưu trữ lớn mà không cần phải nâng cấp khả năng xử lý của hệ thống hiện tại. Tính chất phân tán của mạng ngang hàng cũng giúp cho việc phân tán trách nhiệm cung cấp dịch vụ đến tất cả các node trên mạng, nó sẽ loại bỏ được vấn đề ngừng trệ dịch vụ do nơi cung cấp duy nhất gặp sự cố. Đối với mô hình tập trung, chỉ cần máy chủ gặp sự cố thì cả hệ thống sẽ ngưng trệ.

Còn đối với mạng ngang hàng, máy tính có thể tham gia hoặc rời khỏi mạng bất kỳ lúc nào mà mạng vẫn hoạt động bình thường, các máy tính còn lại vẫn có thể trao đổi thông tin và chia sẻ tài nguyên cho nhau. Bên cạnh nhiều ưu điểm đã được nêu ở trên thì mạng ngang hàng cũng còn tồn tại một số nhược điểm 1.3 Nhƣợc điểm của mạng ngang hàng Do các máy tính trên mạng ngang hàng đều có vai trò như nhau và không tuân theo bất cứ một quy luật định tuyến hay kết nối nào, việc yêu cầu dịch vụ được đáp ứng tuỳ biến nên máy yêu cầu dịch vụ có thể nhận được nhiều kết quả TIEU LUAN MOI download : [e-mail] 10 khác nhau, khi nó kết nối đến nhiều máy tính khác nhau cùng cung cấp một dịch vụ. Các yêu cầu gửi đi có thể không nhận được kết quả trả về vì không có gì đảm bảo sẽ tồn tại một máy nào đó có khả năng đáp ứng yêu cầu đó. Do đặc điểm là các node có thể rời mạng bất kì lúc nào nên có thể bị ngắt kết nối tới các node này bất cứ thời điểm nào.2 Phân loại mạng ngang hàng Mạng ngang hàng có nhiều tiêu trí phân loại khác nhau, trong luận văn này xin được trình bày hai tiêu trí phân loại mạng ngang hàng đó là: Phân loại theo mức độ tập trung của các node mạng và phân loại theo cấu trúc liên kết của các node.1 Phân loại theo mức độ tập trung của các node mạng Nếu lấy tiêu chí về mức độ tập trung của các node mạng, mạng ngang hàng có thể phân làm 2 loại: mạng ngang hàng thuần tuý và mạng ngang hàng lai a.

Mạng ngang hàng thuần tuý Trong mạng ngang hàng thuần tuý thì vai trò của các máy trong mạng là ngang nhau và trong mô hình mạng này đã loại bỏ sự tồn tại của các máy chủ tập trung. Trong mạng này đã khắc phục được vấn đề node nghẽn cổ chai trong mô hình tập trung. Tuy nhiên vấn đề tìm kiếm trong mạng ngang hàng thuần tuý sử dụng cơ chế phát tràn (Flooding), yêu cầu tìm kiếm được gửi tới tất cả các node mạng là láng giềng với nó, điều này làm tăng đáng kể lưu lượng trong mạng. TIEU LUAN MOI download : skknchat@gmail.

Mô hình mạng ngang hàng thuần tuý b. Mạng ngang hàng lai ghép Trong mô hình này, các peer lưu giữ nội dung chia sẻ với các node khác ở trên mạng. Tất cả các peer đều kết nối tới một server, server này lưu giữ thông tin về: - Bảng thông tin kết nối của người dùng đăng kí (địa chỉ IP, băng thông kết nối…) - Bảng liệt kê danh sách các file mà các peer nắm giữ và chia sẻ ở trên mạng cùng với các thông tin mô tả về các files ( tên file, ngày tạo…) Tất cả các peer muốn kết nối vào mạng đều phải liên lạc với server và thông báo với server các file mà nó có. Một peer mà muốn tìm kiềm một file, yêu cầu tìm kiếm được chuyển cho server, server tìm kiếm trong thông tin chỉ mục của mình và trả lại danh sách các peer có thông tin cần tìm.

Peer tìm kiếm sẽ liên lạc trực tiếp với các peer có thông tin theo yêu cầu tìm kiếm để tải thông tin trực tiếp từ các peer này. TIEU LUAN MOI download : skknchat@gmail. Hệ thống mạng ngang hàng lai ghép 1.2 Phân loại theo cấu trúc liên kết Mạng phủ bao gồm tất cả các node mạng đại diện cho các máy tham gia và các liên kết giữa các node mạng này. Một liên kết tồn tại giữa hai node mạng khi một node mạng biết vị trí của node mạng kia.

Dựa vào cấu trúc liên kết trong mạng phủ người ta có thể phân loại mạng ngang hàng thành hai loại: mạng ngang hàng không có cấu trúc và mạng ngang hàng có cấu trúc. Mạng ngang hàng không có cấu trúc Một mạng ngang hàng được gọi là mạng ngang hàng không có cấu trúc khi liên kết giữa các node trong mạng phủ được thiết lập ngẫu nhiên (tức là không theo một quy luật nào cả). Những mạng như vậy dễ dàng xây dựng vì khi một node muốn tham gia mạng có thể lấy liên kết có sẵn của một node khác đang ở trong mạng và sau đó dần dần tự bản thân nó sẽ thêm vào các liên kết mới của riêng mình. Trong mạng ngang hàng không có cấu trúc, khi một node muốn tìm kiếm một dữ liệu, thì yêu cầu tìm kiếm sẽ truyền trên toàn bộ mạng để tìm ra càng nhiều máy tính chia sẻ càng tốt.

Hệ thống này thể hiện rõ nhược điểm là không có gì đảm bảo là việc tìm kiến thành công. Đối với dữ liệu phổ biến được chia sẻ trên nhiều máy thì tỉ lệ thành công là khá cao, ngược lại nếu dữ liệu chỉ được TIEU LUAN MOI download : [e-mail] 13 chia sẻ trong một vài máy thì xác suất tìm thấy là rất nhỏ. Tính chất này là hiển nhiên trong mạng ngang hàng không có cấu trúc vì không có bất kỳ mối tương quan nào giữa một máy và dữ liệu của nó quản lý trong mạng, do vậy yêu cầu tìm kiếm được chuyển một cách ngẫu nhiên đến một số máy trong mạng. Số máy trong mạng càng lớn thì khả năng tìm thấy thông tin càng nhỏ.

Do khi muốn tìm kiếm trên mạng ngang hàng không có cấu trúc, yêu cầu tìm kiếm được phát trên toàn mạng nên không có cấu trúc định hướng, một yêu cầu thường chuyển cho số lượng lớn các máy tính trong mạng làm tiêu tốn băng thông, dẫn đến hiệu quả tìm kiếm thấp. Một mô hình mạng ngang hàng không cấu trúc điển hình đó là mạng Gnutella. Các máy tính trong Gnutella được mô tả như là những “servent”, các thành viên trong mạng và được chia sẻ file. Các máy tính khác có thể lấy được những file chia sẻ này.

Việc tìm kiếm file trên mạng mô tả trong hình 4, khi một máy tính A tìm kiếm file X, nó sẽ gửi một truy vấn broadcast tới tất cả các máy tính nó biết, được coi là hàng xóm của nó. Truy vấn sau đó sẽ được chuyển dần qua các bước và tới được máy tính có chứa file X.