ĐẠ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

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 ..................................................................................... 11
1.1.Bài toán cân bằng tải trong mạng ngang hàng có cấu trúc ..................................... 11
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 ...................................................................................................................... 12
1.3. Hướng tiếp cận của luận văn và kết quả đạt được ................................................ 13
1.4. Cấu trúc của luận văn .......................................................................................... 13
1.5. Kết luận ............................................................................................................... 14
Chương 2. Các kiến thức cơ sở liên quan ....................................................................... 15
2.1. Mạng ngang hàng ................................................................................................ 15
2.1.1. Khái niệm mạng ngang hàng ......................................................................... 15
2.1.2. Các đặc trưng của mạng ngang hàng.............................................................. 16


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 ......................................................... 16
Hình 2.2. Mô hình bảng băm phân tán ....................................................................... 18
Hình 2.3. Không gian định danh 6-bit của Chord ....................................................... 19
Hình 2.4. Vòng tròn định danh Chord với 3 node [6] ................................................. 20
Hình 2.5. Sơ đồ thuật toán di chuyển server ảo nhiều-nhiều ....... Error! Bookmark not
defined.
Hình 3.1. Vòng Chord ban đầu .................................................................................. 28

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
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à

ngang hàng kết hợp băng thông và sức mạnh xử lý để tạo sức mạnh xử lý lớn hơn mà
không cần đầu tư tốn kém về cơ sở hạ tầng như mô hình client/server. Gần đây, các
ứng dụng chia sẻ file và dữ liệu phân tán như Skype, BitTorrent đang được rất nhiều
người sử dụng. Người dùng Skype tăng lên đáng kể: tăng thêm khoảng 2,5 triệu người
tham gia sử dụng trong 1 năm…Hệ thống mạng ngang hàng ra đời đầu tiên là mạng
ngang hàng không có cấu trúc, sau đó là sự ra đời của mạng ngang hàng có cấu trúc
khắc phục những nhược điểm của mạng ngang hàng không có cấu trúc
Các hệ thống mạng ngang hàng không có cấu trúc vẫn còn những hạn chế nhất
định. Với đặc điểm là không có mối liên hệ giữa một máy và dữ liệu nó quản lý, yêu
cầu tìm kiếm được phát tràn cho lượng lớn máy trong mạng ngang hàng không có cấu
trúc đã tiêu tốn băng thông lớn, hiệu quả tìm kiểm thấp. Để nâng cao được hiệu quả
tìm kiếm, tránh tiêu tốn lượng băng thông lớn, người ta sử dụng hệ thống mạng ngang
hàng có cấu trúc. Hệ thống mạng ngang hàng có cấu trúc sử dụng bảng băm phân tán
(DHT) để tổ chức các máy (node) trong hệ thống mạng một cách hiệu quả như cấu trúc
CAN, Partry, Chord… Trong đó, cấu trúc vòng Chord tổ chức không gian định danh
và định tuyến truy vấn đơn giản hơn, hiệu quả hơn. Nó ràng buộc các node trong mạng
và dữ liệu mà node quản lý bằng cách gán cho chúng định danh (ID) và khóa (key),
mỗi node mạng sẽ chịu trách nhiệm với phần dữ liệu nào đó trong mạng. Khi đó, nếu
một máy cần tìm dữ liệu nào đó, nó chỉ cần sử dụng giao thức chung để xác định node
chịu trách nhiệm cho dữ liệu đó và liên lạc trực tiếp đến node đó để lấy dữ liệu.
Song, thực tế cho thấy rằng nếu đạt được giả thiết là khả năng của các node
giống nhau, các node và dữ liệu trên không gian định danh được phân bố một cách
đồng đều, số truy vấn đến các dữ liệu cũng đồng đều thì các hệ thống mạng ngang
hàng có cấu trúc này mới thực sự hoạt động hiệu quả. Do các node tham gia vào mạng
một cách ngẫu nhiên, tùy tiện nên các điều kiện giả thiết trên sẽ không bao giờ đạt
11


được. Khi đó, các hệ thống mạng ngang hàng có cấu trúc rất dễ bị mất cân bằng tải
giữa các node, làm mất hiệu quả trong việc truy vấn, tìm kiếm. Với yêu cầu thực tế đặt

sẽ hoạt động kém hiệu quả.
Trước đó, tác giả Nguyễn Thị Mi – tác giả một khóa luận tốt nghiệp đại học
trường Đại học Công nghệ đã đưa ra một phương pháp cân bằng tải phi tập trung [3].
12


Nhưng theo phương pháp này, một node vật lý sẽ phải lưu thông tin về tất cả các node
vật lý có trong mạng và các server ảo gây nặng tải. Khi truyền tin, các node phải gửi
thông báo cho tất cả các node khác trong mạng. Điều này sẽ gây lãng phí băng thông,
làm cho thuật toán cân bằng tải vẫn chưa thực sự hiệu quả và có kết quả mô phỏng
thấp hơn thuật toán di chuyển server ảo nhiều-nhiều.
1.3. Hướng tiếp cận của luận văn và kết quả đạt được
Luận văn giải quyết vấn đề cân bằng tải trong mạng ngang hàng có cấu trúc
theo hướng sử dụng server ảo. Luận văn đưa ra một giải pháp cân bằng tải phi tập
trung dựa trên server ảo, khắc phục nhược điểm tập trung hóa của phương pháp di
chuyển server ảo nhiều-nhiều. Dựa vào độ lệch tải của các node trên vòng Chord cũ, ta
đi xây dựng vòng Chord mới. Sau đó thực hiện các bước cân bằng tải trong vòng
Chord mới này. Giải pháp cân bằng tải mới này cho những kết quả cân bằng tải ngang
bằng thuật toán di chuyển server ảo nhiều-nhiều, mà không làm mất tính phi tập trung
của hệ thống mạng ngang hàng.
Chúng tôi đã thực hiện mô phỏng giải pháp mới dựa trên mô phỏng của tác giả
Jonanthan Ledlie – tác giả đã đi xây dựng bộ mô phỏng cho các phương pháp cân bằng
tải: k-choices, di chuyển server ảo một-một, threshold, proportional [5] và tác giả
Nguyễn Thị Mi – tác giả đã mô phỏng thêm thuật toán di chuyển server ảo nhiều-nhiều
[3]. Kết quả mô phỏng thu được cho thấy giải pháp cân bằng tải mới có hiệu quả
ngang bằng thuật toán di chuyển server ảo nhiều-nhiều.
1.4. Cấu trúc của luận văn
Nội dung của luận văn gồm 4 chương:
Chương 1. Giới thiệu tổng quan
Giới thiệu bài toán cân bằng tải trong mạng ngang hàng có cấu trúc, trình bày

nay, hướng tiếp cận, nêu ra giải pháp cân bằng tải mới phi tập trung, kết quả đạt được
và cấu trúc của luận văn.

14


Chương 2. Các kiến thức cơ sở liên quan
2.1. Mạng ngang hàng
2.1.1. Khái niệm mạng ngang hàng
“Trong vài năm gần đây, số lượng các hệ thống phân tán tăng lên một cách ồ ạt
với hàng triệu người tham gia đã xuất hiện trong một thời gian ngắn. Các ứng dụng
như tin nhắn nhanh (IM), chia sẻ file và nội dung phân tán đang thu hút vô số người
tham gia sử dụng. ví dụ dịch vụ Skype đã tăng thêm hơn 2,5 triệu người sử dụng trong
vòng một năm, và hơn 50% lưu lượng Internet tăng thêm có nguồn gốc từ BitTorrent.
Chúng phát triển một cách nhanh chóng tạo nên một kỷ nguyên mới cho việc thiết kế
và triển khai các hệ thống mạng ngang hàng”. [3]
Tốc độ phát triển Internet nhanh khiến mô hình client/server bộc lộ nhiều nhược
điểm khi số máy client tham gia vào mạng tăng lên đáng kể. Server sẽ phải cung cấp
dịch vụ cho các client. Đến một mức nào đó, khi có quá nhiều yêu cầu từ các client,
server sẽ không thể đáp ứng kịp thời và sẽ bị quá tải. Điều này có thể dẫn đến sập toàn
hệ thống mạng. Như vậy, mô hình client/server không có khả năng mở rộng. Trong khi
đó, mạng ngang hàng có khả năng mở rộng, càng nhiều máy tham gia vào mạng càng
tốt.
Mạng ngang hàng (peer-to-peer) hoạt động dựa vào băng thông và sức mạnh
tính toán của các máy tham gia. Trên mạng ngang hàng, ta không có khái niệm client
hoặc server, các máy tham gia vào mạng có vai trò bình đẳng, việc quản lý mạng
không tập trung ở một số máy server trung tâm như mạng client/server. Sức mạnh xử
lý của hệ thống sẽ là tổng sức mạnh xử lý của các máy tham gia vào mạng. Như vậy,
mạng ngang hàng có khả năng mở rộng, đáp ứng nhu cầu phát triển của Internet.
Mô hình mạng ngang hàng rất phù hợp với tính phi tập trung của Internet. Nó

2.1.3. Các loại mạng ngang hàng

Các loại mạng ngang hàng được phân chia trong hình 2.1

Hình 2.1. Phân loại hệ thống mạng ngang hàng [1]
16


Tùy theo mục đích phân loại, ta có thể phân chia thành các loại mạng ngang
hàng. Nếu dựa vào sự liên kết giữa các node trong mạng ta có thể phân thành hai loại
mạng ngang hàng: không có cấu trúc và có cấu trúc.
Trong mạng ngang hàng không có cấu trúc, liên kết giữa các node được thiết
lập ngẫu nhiên, không theo một quy luật nào. Khi có yêu cầu tìm kiếm, gói tin tìm
kiếm sẽ được truyền boardcast. Nếu quy mô mạng lớn, có thể yêu cầu tìm kiếm này sẽ
không thành công do gói tin tìm kiếm chưa đến được đích thì TTL = 0 và gói tin sẽ bị
loại bỏ. Như vậy, nếu dữ liệu cần tìm chỉ được chia sẻ trên một vài máy thì xác suất
tìm kiếm là khá thấp, không có gì bảo đảm node lưu trữ dữ liệu cần tìm còn tồn tại
trong mạng hay không và như thế sẽ không có gì đảm bảo tìm kiếm sẽ thành công.
Bên cạnh đó, do không có định hướng, gói tin tìm kiếm sẽ được phát tràn trên mạng
gây tốn kém băng thông của hệ thống.
Với mạng ngang hàng có cấu trúc, những nhược điểm trên sẽ được khắc phục
bằng cách sử dụng bảng băm phân tán (DHT). Các node trong mạng được liên kết chặt
chẽ theo thuật toán cụ thể. Mỗi node sẽ quản lý một phần dữ liệu. Do đó, khi có yêu
cầu tìm kiếm, node mạng chỉ cần xác định node nào đó chịu trách nhiệm cho dữ liệu
cần tìm, sau đó liên lạc trực tiếp đến node đó để lấy dữ liệu. Như thế, khả năng mở
rộng của mạng ngang hàng có cấu trúc là rất lớn, các node tham gia hay rời bỏ mạng
cũng dễ kiểm soát hơn.
2.2. Bảng băm phân tán (DHT)
Bảng băm phân tán (Distributed Hash Table) phân tán dữ liệu trên các node và
thực hiện định tuyến cho việc tìm kiếm. Mỗi node trong DHT sẽ chịu trách nhiệm một



hàm băm là hàm băm SHA-1, duy trì các thông tin dò đường bằng các bảng định
tuyến, các cơ chế ổn định mạng khi có các node tham gia hay rời khỏi mạng.
2.3.2. Không gian định danh
DHT có các khóa là các định danh có độ dài m bit, đó là các số nguyên trong
khoảng [0, 2m – 1]. Chúng tạo thành một vòng tròn định danh một chiều modulo 2m và
nhận các giá trị trong khoảng từ 2m – 1 đến 0.
Chord được mô tả như một vòng tròn. Nếu số bit định danh của không gian mạng
Chord là n thì nó có thể chứa tối đa 2n node. Node và dữ liệu sẽ được gán một định
danh tương ứng, là các giá trị từ việc băm địa chỉ IP đối với node trong mạng và băm
các tên file hoặc cả nội dung file đối với dữ liệu. Định danh của node là một địa chỉ
trong mạng (ID). Còn định danh của dữ liệu là một khóa (key). Node trong vòng
Chord sẽ có các ID tăng dần theo chiều kim đồng hồ. Node sẽ duy trì liên kết hai chiều
với node liền trước và node liền sau nó tạo thành một mạch liên kết vòng. Các ID của
node sẽ chịu trách nhiệm quản lý tất cả các key đứng trước nó. Một cặp (k,v) k: key,
v:value đặc trưng cho dữ liệu sẽ được quản lý bởi node gần nhất tiếp theo có ID ≥ k.
Node đó gọi là successor của key k. Còn node đứng liền trước trong vòng tròn Chord
thì được gọi là predecessor.

Hình 2.3. Không gian định danh 6-bit của Chord [3]
2.3.3.Định tuyến
Mọi định danh trên Chord được sắp sếp theo trật tự. Nhờ vào việc sử dụng
DHT, các node trong Chord không cần biết tất cả các node trong mạng. Mỗi node chỉ
cần biết một số nhỏ thông tin định tuyến về các node khác trong bảng định tuyến của
mình. Mỗi cặp (k,v) chỉ được quản lý ở một node. Để tìm kiếm hiệu quả và nhanh
chóng thì cần tìm ra node chịu trách nhiệm quản lý key nào đó. Trên vòng định danh,
19



2.3.5. Cơ chế ổn định mạng trong vòng Chord
Do các node tham gia và rời bỏ mạng một cách tùy tiện nên Chord đưa ra cơ
chế ổn định mạng. Một node n muốn tham gia vào mạng, nó sẽ cần biết một node m đã
tham gia vào mạng rồi. Để node n tìm được successor của nó, node n sẽ truy vấn đên
node m chính ID của n. Khi đó, node n sẽ xây dựng bảng định tuyến của nó bằng cách
lặp lại truy vấn đến node m để tìm các successor của các node n+21, n+22, n+23,…
Để ổn định mạng thì tất cả các node phải thực hiện định kỳ cơ chế ổn định.
Trong đó, một node n sẽ yêu cầu successor của nó trả về predecessor h, nếu h chính là
node n thì n và successor của n vẫn sẽ là predecessor và successor của nhau, nếu h
nằm giữa n và successor của n thì n sẽ cập nhật h vừa tham gia vào mạng với tư cách
là successor của n. Sau khi node n đã biết predecessor, nó sẽ chép tất cả các khóa mà
nó chịu trách nhiệm nằm giữa predecessor(n) và n. Predecessor(n) sẽ giải phóng các
khóa này. Cứ như thế, sau một thời gian các con trỏ successor sẽ được cập nhật, hệ
thống được ổn định. Số node cần cập nhật bảng định tuyến là O(log(N)), trong đó N là
số node trong hệ thống.
2.4. Khái niệm liên quan đến tảiError! Reference source not found.
Để quản lý nhiều phân vùng khác nhau của không gian địa chỉ DHT trên cùng
node vật lý thì người ta dùng khái niệm server ảo (virtual server) [4]. Trong Chord,

21


một node vật lý có thể có nhiều server ảo. Mỗi server ảo quản lý một khoảng không
gian địa chỉ, còn node vật lý tương ứng với nó sẽ quản lý một vài khoảng độc lập.
Tải của một server ảo được xác định bởi số lượng dữ liệu mà nó lưu trữ. Tải của
một node vật lý là tổng của tất cả dữ liệu trên các server ảo thuộc nó quản lý. Như vậy,
tổng tải của cả hệ thống là tổng của các node tham gia vào mạng. Nếu hệ thống gồm N
node và khả năng của mỗi node giống nhau về băng thông, bộ nhớ, khả năng xử lý của
CPU.., để đạt trạng thái cân bằng tối ưu thì tải của từng node bằng 1/N tổng tải hệ
thống. Node nặng tải (overload) là node có tải cao hơn hẳn tải của các node khác trong



chuyển hết cho successor của nó. Nếu hiện tại successor đó đang đủ tải thì
điều này gây nặng tải cho nó.
2.6. Các phương pháp cân bằng tải hiện nay
Hiện nay trong mạng ngang hàng có cấu trúc đã có nhiều phương pháp cân
bằng tải sử dụng server ảo như k-choices [5], log (N) server ảo [5], di chuyển server
ảo: một-một, một-nhiều, nhiều-nhiều [6]… Các phương pháp di chuyển server ảo được
đánh giá là có kết quả tốt hơn các phương pháp cân bằng tải sử dụng server ảo còn lại.
Ở đây, trong khuôn khổ luận văn tôi xin đi tìm hiểu về các phương pháp cân bằng tải
di chuyển server ảo.
Các thuật toán này thực hiện cân bằng tải bằng cách di chuyển server ảo từ
node nặng tải sang node nhẹ tải. Khi chuyển server ảo từ node nặng tải h sang node
nhẹ tải l một server ảo là v thì phải thỏa mãn ba quy tắc dưới đây:
-

Chuyển server ảo v từ node h sang node l không làm cho node l nặng tải

-

Server ảo v có tải nhẹ nhất mà sau khi chuyển làm cho node h nhẹ tải
Nếu không có server ảo chuyển đi làm cho node h nhẹ tải thì chuyển
server ảo nặng tải nhất từ node h sang node l

Các phương pháp này cố gắng chuyển lượng tải nhỏ nhất có thể để làm cho
node nặng tải trở thành node nhẹ tải mà không thể làm cho node nhẹ tải nhận server ảo
không bị nặng tải. Nếu như không tìm được server ảo nào thỏa mãn thì chọn server ảo
nặng tải nhất của node nặng tải chuyển sang node nhẹ tải mà vẫn không làm node nhẹ
tải trở thành nặng tải. Như thế node nặng tải sẽ có thêm cơ hội để tìm node nhẹ tải
khác có thể chấp nhận tất cả các tải dư thừa của nó.

Phương pháp này thực hiện 3 giai đoạn: Loại bỏ tải dư thừa, Chèn và Hoán đổi.
-

Loại bỏ dư thừa: Ở giai đoạn loại bỏ tải dư thừa, tất cả các node đều trở
thành nhẹ tải bởi vì node nặng tải sẽ chuyển server ảo gây nặng tải cho
nó tới global pool đến khi trở thành nhẹ tải.

-

Chèn: Đến giai đoạn chèn, các server ảo từ global pool sẽ được chuyển
đến các node nhẹ tải sao cho không có node nào nặng tải. Đầu tiên, ta
chọn một server ảo nặng tải nhất từ global pool, chuyển nó đến node nhẹ
tải phù hợp nhất. Cứ thế, các server ảo sẽ được chuyển đi hết, hoặc
không thể chèn server ảo ở global pool vào bất kỳ node nhẹ tải nào. Nếu
không còn server ảo nào trong global pool thì kết thúc. Ngược lại,
chuyển sang giai đoạn hoán đổi.

-

Hoán đổi: Ở giai đoạn hoán đổi, server ảo nặng tải nhất v trong global
pool sẽ được hoán đổi với một server ảo v’nhẹ tải nhất của một node nhẹ
tải m sao cho Lm + load(v) – load(v’) ≤ Tm. Nếu hoán đổi được thì quay
lại bước chèn. Ngược lại, thuật toán kết thúc.

Như vậy, trong chương này ta đã tìm hiểu được những định nghĩa cơ bản về cân
bằng tải và các nguyên nhân cơ bản dẫn đến việc mất cân bằng tải trên các hệ thống
mạng ngang hàng có cấu trúc là do khả năng của các node tham gia vào mạng không
đồng đều, định danh node, định danh dữ liệu phân bố không đồng đều, truy vấn trên
24