- ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ. - MỘT PHƯƠNG PHÁP PHI TẬP TRUNG CHO CÂN BẰNG TẢI TRONG CÁC MẠNG NGANG HÀNG. - CÓ CẤU TRÚC. - LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN. - Tôi xin gửi lời cảm ơn sâu sắc tới TS.Nguyễn Đại Thọ, Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội, người thầy đã dành nhiều thời gian tận tình chỉ bảo, hướng dẫn, giúp đỡ tôi trong suốt quá trình tìm hiểu, nghiên cứu.. - Tôi xin chân thành cảm các thầy, cô ở khoa Công nghệ thông tin – Trường Đại học Công nghệ - ĐHQGHN đã cung cấp cho tôi kiến thức và tạo cho tôi những điều kiện thuận lợi trong suốt quá trình tôi học tập tại trường.. - 1.1.Bài toán cân bằng tải trong mạng ngang hàng có cấu trúcError! Bookmark not defined.. - 1.2.Một số hướng nghiên cứu về cân bằng tải trong mạng ngang hàng có cấu trúc. - Cấu trúc của luận văn. - Mạng ngang hàng. - Khái niệm mạng ngang hàng. - Các đặc trưng của mạng ngang hàng. - Các loại mạng ngang hàng. - Không gian định danh. - 2.3.4.Truy vấn trong vòng Chord. - Nguyên nhân gây mất cân bằng tải. - Các phương pháp cân bằng tải hiện nay. - 2.6.1.Phương pháp di chuyển server ảo một-một. - 2.6.2.Phương pháp di chuyển server ảo một-nhiều. - 2.6.3.Phương pháp di chuyển server ảo nhiều-nhiều. - Giải pháp cân bằng tải phi tập trung mới. - Mô tả mô phỏng của giải pháp cân bằng tải mới. - Lượng truy vấn trên một node thay đổi. - Độ lệch trong truy vấn giữa các node thay đổi. - Phân loại hệ thống mạng ngang hàng. - Sơ đồ thuật toán di chuyển server ảo nhiều-nhiều. - Vòng Chord mới. - Sơ đồ thuật toán của giải pháp mới. - Tỷ lệ phần trăm truy vấn thành công khi lượng tải thay đổi (truy vấn dạng Uniform. - Tỷ lệ phần trăm truy vấn thành công khi lượng tải thay đổi (truy vấn dạng Zipf 0.8. - Tỷ lệ phần trăm truy vấn thành công khi lượng tải thay đổi (truy vấn dạng Zipf 1.2. - Tỷ lệ phần trăm truy vấn thành công khi độ skew của mạng thay đổi. - Khắc phục những nhược điểm đó, mạng ngang hàng ra đời.. - Mạng ngang hàng có 2 loại: không cấu trúc và có cấu trúc. - Với mạng ngang hàng không có cấu trúc, không có mối liên hệ nào giữa một máy và dữ liệu của nó.. - Mặt khác, trong mạng ngang hàng không có cấu trúc, các package tìm kiểm thường được chuyển phát tràn tới lượng lớn các máy gây ra việc tốn lượng băng thông lớn. - Với mạng ngang hàng có cấu trúc, những hạn chế đó đã được khắc phục bằng cách sử dụng bảng băm phân tán (DHT). - Nó định nghĩa liên kết giữa các node mạng theo một thuật toán cụ thể, các node lưu trữ dữ liệu được phân bố một cách hiệu quả, đồng thời xác định mỗi node mạng sẽ chịu trách nhiệm đối với một phần dữ liệu trong mạng một cách chặt chẽ. - Đã có nhiều cấu trúc mạng ngang hàng sử dụng DHT như CAN, Chord, Partry… Trong đó, Chord được sử dụng nhiều hơn trong nghiên cứu về tối ưu mạng và cân bằng tải vì Chord tổ chức không gian định danh và định tuyến một cách đơn giản, hiệu quả.. - Theo những nghiên cứu trước, mạng ngang hàng có cấu trúc hoạt động hiệu quả khi các máy (node) và dữ liệu được phân bố trên không gian định danh đồng đều, số truy vấn đến các dữ liệu ngang nhau, khả năng của các node giống nhau…Tuy nhiên, thực tế các node tham gia vào mạng là ngẫu nhiên, nên các giả thiết trên sẽ không bao giờ xảy ra. - Do đó, hệ thống mạng sẽ bị mất cân bằng tải.. - Hiện nay nhiều nghiên cứu về cân bằng tải đã được đề xuất theo hai hướng:. - không sử dụng server ảo và có sử dụng server ảo. - Trong luận văn này, tôi xin đi theo hướng nghiên cứu về cân bằng tải sử dụng server ảo trong mạng ngang hàng có cấu. - Một số phương pháp cân bằng tải dựa trên server ảo tiêu biểu như di chuyển server ảo, log(N) server ảo, k-choices. - Với các phương pháp cân bằng tải di chuyển server ảo, mỗi server vật lý quản lý một số server ảo. - Nếu có một server vật lý nặng tải, ta sẽ di chuyển server ảo từ server vật lý đó sang server vật lý nhẹ tải, đảm bảo sau khi chuyển thì hai server đó cùng nhẹ tải. - Ứng với việc di chuyển server ảo, ta có ba thuật toán di chuyển: một-một, một-nhiều, nhiều-nhiều. - Trong thuật toán di chuyển server ảo một-một, server vật lý nhẹ tải sẽ chọn một định danh ID bất kỳ, và kiểm tra xem node có ID đó là nặng tải hay nhẹ tải, nếu node là nặng tải thì bắt đầu thực hiện chuyển server ảo. - Trong thuật toán di chuyển server ảo một-nhiều, server vật lý nhẹ tải sẽ thông báo tải của nó cho directory, còn server vật lý nặng tải sẽ lấy thông tin về các server vật lý nhẹ tải từ directory, sau đó xác định server vật lý nhẹ tải thỏa mãn để di chuyển server ảo. - Trong thuật toán di chuyển server ảo nhiều-nhiều, global pool được sử dụng để quản lý các server ảo, một bước trung gian để chuyển server ảo từ node nặng tải sang node nhẹ tải. - Global pool chỉ là một cấu trúc dữ liệu cục bộ được sử dụng để tính toán cấp phát cuối cùng, sẽ không có tải nào được chuyển cho đến khi thuật toán kết thúc. - Đây chính là hạn chế của thuật toán này, phá vỡ tính phi tập trung của mạng ngang hàng. - Vấn đề đặt ra ở đây là phải đưa ra phương pháp cân bằng tải khắc phục được nhược điểm tập trung hóa của thuật toán cân bằng tải di chuyển server ảo nhiều-nhiều.. - Xuất phát từ yêu cầu đặt ra, tôi xin đưa ra một giải pháp mới cân bằng tải phi tập trung dựa trên server ảo bằng cách xây dựng thêm vòng Chord mới dựa vào độ lệch tải của các node trên vòng Chord cũ. - Kết quả mô phỏng của chúng tôi cho thấy rằng hiệu quả của giải pháp mới gần xấp xỉ hiệu quả của thuật toán cân bằng tải nhiều-nhiều.. - [1] Bùi Thị Lệ Hằng (2009), Sử dụng thông tin gần kề vị trí trong khảo duyệt web, Luận văn thạc sĩ trường Đại học Công nghệ, Đại học Quốc gia Hà Nội.. - [2] Lê Anh Tuấn (2014), Định tuyến an toàn trong cấu trúc bảng băm phân tán Chord kép, Luận văn thạc sĩ trường Đại học Công nghệ, Đại học Quốc gia Hà Nội.. - [3] Nguyễn Thị Mi (2009), Cân bằng tải trong các mạng ngang hàng có cấu trúc, Khóa luận tốt nghiệp đại học trường Đại học Công nghệ, Đại học Quốc gia Hà Nội