ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THỊ HỒNG HIÊN

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

Hà Nội - 2015


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THỊ HỒNG HIÊN

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

Ngành:

Công nghệ Thông tin

Chuyên ngành: Hệ thống Thông tin
Mã số:

60480104

LỜI CAM ĐOAN
Tôi xin cam đoan đây là đề tài nghiên cứu của riêng tôi, thực hiện dưới sự hướng
dẫn của TS. Nguyễn Đại Thọ.
Các kết quả nêu trong luận văn là trung thực và chưa được ai công bố trong bất
cứ công trình nào khác.

Hà Nội, tháng 6 năm 2015
Học viên

Nguyễn Thị Hồng Hiên

4


MỤC LỤC
LỜI CẢM ƠN ...................................................................................................................... 3
MỤC LỤC ........................................................................................................................... 5
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ......................................................... 7
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ............................................................................. 8
LỜI MỞ ĐẦU ..................................................................................................................... 9
Chương 1. Giới thiệu tổng quan ........................................ Error! Bookmark not defined.
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
hiện nay ............................................................................. Error! Bookmark not defined.
1.3. Hướng tiếp cận của luận văn và kết quả đạt được ..... Error! Bookmark not defined.
1.4. Cấu trúc của luận văn ................................................. Error! Bookmark not defined.
1.5. Kết luận ...................................................................... Error! Bookmark not defined.
Chương 2. Các kiến thức cơ sở liên quan.......................... Error! Bookmark not defined.
2.1. Mạng ngang hàng ....................................................... Error! Bookmark not defined.
2.1.1. Khái niệm mạng ngang hàng ............................... Error! Bookmark not defined.

. .......................................................................................................................................... 12

6


DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
Viết tắt
PS
VS
DHT
DHTs
ID

Ý nghĩa
Physical Server
Virtual Server
Distributed Hash Table
Distributed Hash Tables
Identifier

7


DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 2.1. Phân loại hệ thống mạng ngang hàng ............ Error! Bookmark not defined.
Hình 2.2. Mô hình bảng băm phân tán .......................... Error! Bookmark not defined.
Hình 2.3. Không gian định danh 6-bit của Chord ......... Error! Bookmark not defined.
Hình 2.4. Vòng tròn định danh Chord với 3 node [6] ... Error! Bookmark not defined.
Hình 2.5. Sơ đồ thuật toán di chuyển server ảo nhiều-nhiều ...... Error! Bookmark not
defined.

yêu cầu tìm kiếm sẽ bị loại bỏ. Một yêu cầu tìm kiếm có thể sẽ không nhận được kết
quả, do không có gì đảm bảo một máy nào đó có khả năng đáp ứng yêu cầu đó sẽ tồn
tại. 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. Các node là các máy tính cá nhân, không phải lúc nào các máy này cũng
tham gia vào mạng nên có thể tài nguyên của node đó sẽ biến mất trong một khoảng
thời gian nào đó. 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
9


trúc Chord. 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

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
11


Tiếng Anh
[4] A. Rao, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica. Load Balancing
in Structured P2P Systems. In Proceedings of the Second International Workshop
on Peer-to-Peer Systems (IPTPS ’03), Berkeley, CA, February 2003.
[5] J. Ledlie and M. Seltzer. Distributed, secure load balancing with skew,
heterogeneity, and churn. Technical Report TR-31-04, Harvard University, December
2004.
[6] Sonesh Surana, Brighten Godfrey, Karthik Lakshminarayanan, Richard Karp, Ion
Stoica (2004), Load Balancing in Dynamic Structured Peer-to-peer Systems.
[7] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A
scalable peer-to-peer lookup service for internet applications. In Proceedings of the
ACM SIGCOMM ’01 Conference, August 2001.

.

12