LỜI CAM ĐOAN
Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả
nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công
trình nào khác.
Tác giả luận văn ký và ghi rõ họ tên
Mai Quốc Duy
LỜI CẢM ƠN
Đầu tiên, tôi xin chân thành bày tỏ lòng kính trọng và biết ơn sâu sắc đến
thầy TS. Võ Văn Khang đã nhiệt tình hướng dẫn tôi hoàn thành luận văn này. Kể từ
lúc tôi đề xuất đề tài với thầy cho tới hôm nay, thầy đã dành nhiều thời gian để
hướng dẫn phương pháp nghiên cứu khoa học, xác định mục tiêu của đề tài và đặc
biệt là luôn theo sát tiến độ nghiên cứu của tôi để có những góp ý kịp thời. Ngoài
những kiến thức thầy truyền đạt, tôi còn học được ở thầy một phong cách làm việc
rất khoa học, nghiêm túc và đầy trách nhiệm.
Tiếp theo, tôi vô cùng cảm ơn anh em kỹ thuật đang làm việc tại công ty
NetNam đã tạo điều kiện tốt nhất để tôi có thể ứng dụng kết quả luận văn vào môi
trường thực tế. Những lúc ngoài giờ, những anh em này đã cùng tôi xây dựng hệ
thống test trên mạng nội bộ của công ty. Chính nhờ vậy mà tôi đã có cơ hội kiểm
chứng được tính hiệu quả của giải thuật cũng như chương trình cân bằng tải đã đề
2.2 Phân loại 9
2.3 Chức năng của cân bằng tải kết nối (link load-balancer) 10
2.4 Giải thuật và mô hình 11
2.4.1 Xoay vòng (round-robin) 11
2.4.2 Xoay vòng theo trọng số (Weighted round-robin ) 13
2.4.3 Độ ưu tiên (Priority) 15
2.4.4 Tràn băng thông (overflow) 17
2.4.5 Băng thông sử dụng thấp nhất (Least used) 19
2.4.6 Băng thông sử dụng thấp nhất theo trọng số (Weighted least used) 21
2.4.6 Số kết nối thấp nhất (Least connection) 23
2.4.7 Số kết nối thấp nhất theo trọng số (Weighted least connection) 25
2.4.8 Độ trễ thấp nhất (“Lowest latency” hay “Fastest repsonse time”) 27
2.4.8 Cố định hướng truyền dữ liệu (Enforced) 29
2.5 Giải thuật đề xuất 30
2.5.1 Đặt vấn đề 30
2.5.2 Ví dụ so sánh giữa giải thuật đã biết và giải thuật đề xuất 31
2.5.3 Nguyên lý hoạt động của giải thuật mới – “Best QoS” 33
ii
2.5.4 Đánh giá giải thuật “Best QoS” 34
Chương 3 XÂY DỰNG PHẦN MỀM CÂN BẰNG TẢI DỰA VÀO GIẢI THUẬT
ĐỀ XUẤT 35
3.1 Ý tưởng chương trình 35
3.2 Nội dung chương trình 36
3.2.1 Class Main 37
3.2.2 Class Routing 39
3.2.3 Class Loadbalancer 44
3.2.4 Class DatabaseUpdate 51
3.3 Đánh giá chương trình 57
Chương 4 KẾT QUẢ TEST TRONG MÔI TRƯỜNG THỬ NGHIỆM VÀ THỰC
Bảng 2.1: Cách phân phối gói tin trong giải thuật “xoay vòng” (round-robin) 12
Bảng 2. 2:Cách phân phối gói tin trong giải thuật “xoay vòng theo trọng số”
(weighted round-robin) 14
Bảng 2.3: Vài giải thuật cân bằng tải thông dụng hiện nay 30
Bảng 4.1: Danh sách thiết bị cần thiết cho lab ảo VMWare 59
v
DANH MỤC HÌNH VẼ
Hình 2.1: Công việc của bộ cân tải (load-balancer) 7
Hình 2.2: Ví dụ về cân bằng tải kết nối (link load-balancer) 9
Hình 2.3: Tổng quát về cân bằng tải kết nối (link load-balancer) 10
Hình 2.4: Giải thuật “xoay vòng” (round-robin) 11
Hình 2.5: Giải thuật “xoay vòng theo trọng số” (weighted round-robin) 13
Hình 2.6: Giải thuật “độ ưu tiên” (priority) 15
Hình 2.7: Nguyên lý hoạt động của giải thuật “độ ưu tiên” (priority) 16
Hình 2.8: Giải thuật “tràn băng thông” (overflow) 17
Hình 2.9: Nguyên lý hoạt động của giải thuật “tràn băng thông” (overflow) 18
Hình 2.10: Giải thuật “băng thông sử dụng thấp nhất” (least-used) 19
Hình 2.11: Nguyên lý hoạt động của giải thuật “băng thông sử dụng thấp nhất”
(least-used) 20
Hình 2.12: Giải thuật “băng thông sử dụng thấp nhất theo trọng số” (Weighted least
used) 21
Hình 2.13: Nguyên lý hoạt động của giải thuật “băng thông sử dụng thấp nhất theo
trọng số” (Weighted least used) 22
Hình 2.14: Giải thuật “số kết nối thấp nhất” (Least Connection) 23
Hình 2.15: Nguyên lý hoạt động của giải thuật “số kết nối thấp nhất” (Least
Connection) 24
Hình 2.16: Giải thuật “Số kết nối thấp nhất theo trọng số” (weighted least
connection) 25
Hình 2.17: Nguyên lý hoạt động của giải thuật “Số kết nối thấp nhất theo trọng số”
Hình 3.21: Phương thức parseIPFromDatabaseLine() của class DatabaseUpdate 52
Hình 3.22: Phương thức parseQoSFromDatabaseLine() của class DatabaseUpdate53
Hình 3.23: Phương thức lookupDatabase() của class DatabaseUpdate 54
Hình 3.24: Phương thức compareQoSInDatabaseAndBest QoS() của class
DatabaseUpdate 55
Hình 3.25: Phương thức deleteLineInDatabaseFile() của class DatabaseUpdate 55
Hình 3.26: Phương thức addInfoToGuessDabase() của class DatabaseUpdate 56
vii
Hình 3. 27: Phương thức run() của class DatabaseUpdate 57
Hình 4.1: Mô hình lab ảo VMWare 58
Hình 4.2: Mô hình lab thật tại công ty NetNam 60
Hình 4.3: Kịch bản 1 (Test khả năng chọn hướng có Best QoS) 60
Hình 4.4: Kịch bản 2 (Test khả năng tự thay đổi hướng truyền dữ liệu khi Best QoS
thay đổi hoặc băng thông sắp nghẽn) 63
1
Chương 1
GIỚI THIỆU
Chương 1 giới thiệu chung về hiện trạng, nhu cầu và xu hướng chọn lựa giải
thuật cân bằng tải trong hệ thống mạng. Chương này cũng trình bày mục tiêu, đối
tượng và phạm vi nghiên cứu. Cuối chương nêu tóm tắt bố cục của toàn luận văn.
1.1 Hiện trạng
Ngày nay, mạng internet là một thành phần không thể thiếu của hầu hết các
doanh nghiệp. Nhờ có internet mà các công ty có thể giao dịch kinh doanh với thế
giới bên ngoài một cách nhanh chóng, hiệu quả. Nói cách khác, internet đã trở thành
một nhu cầu thiết yếu cho sự phát triển của các tổ chức. Nếu hệ thống internet của
doanh nghiệp bị lỗi, chắc chắn hoạt động kinh doanh sẽ gặp rất nhiều khó khăn. Do
Bảng 1.1: Vài giải thuật cân bằng tải hiện nay
STT
Tên giải thuật cân bằng tải
Tiêu chí cân bằng tải
1
Round robin (RR)
Băng thông
2
Weighted round robin (WRR)
3
Least used
4
Fastest response time (FRT)
Độ trễ
Loại 1, 2 và 3 trong bảng 1.1 chỉ dựa vào yếu tố băng thông để cân tải. Ba
loại này thuộc nhóm “cân tải để lưu lượng chạy đồng thời”. Trong khi đó, loại 4 lại
dựa vào tiêu chí độ trễ để truyền lưu lượng. Nếu chỉ dựa vào thời gian đáp ứng thôi
thì chưa thể xếp loại này vào nhóm “cân tải để lưu lượng chạy hiệu quả” (vì giả sử
đường truyền 1 luôn có độ trễ tốt nhất thì tất cả lưu lượng đều đi qua đường truyền
1? Nếu như thế thì không thể hiện sự cân tải trong giải thuật này. Hoặc nếu đường
truyền 1 có độ trễ tốt nhưng tỉ lệ rớt gói cao thì sao? )
Tóm lại, hiện nay chưa có một giải thuật nào thuộc nhóm “cân tải để lưu
lượng chạy hiệu quả”. Bắt kịp xu thế hiện tại, cũng như nắm được mong muốn của
3
các doanh nghiệp, trong luận văn này em sẽ trình bày một giải thuật mới với mục
tiêu sẽ cân tải thật sự hiệu quả hơn các giải thuật đã được biết trước đây.
1.3 Mục tiêu nghiên cứu
ty đang làm cho phép công bố rộng rãi)
Cách thu thập các thông số của đường truyền:
Đối với thông số độ trễ, tỉ lệ rớt gói, biến thiên độ trễ đến một IP đích
cụ thể: sẽ sử dụng giao thức ICMP. Trong trường hợp IP đích cấm
ICMP thì chính sách cân bằng tải sẽ dựa vào thông số băng thông (bỏ
qua các thông số còn lại).
Đối với thông số bandwidth hiện hành của mỗi interface: Sẽ có một
script để tính toán băng thông hiện tại dựa vào các file liên quan trong
hệ điều hành linux.
1.4 Đối tượng và phạm vi nghiên cứu
Đối tượng:
Lập trình mạng với Java
Định tuyến trên linux
Phạm vi:
Xây dựng chương trình bằng ngôn ngữ Java
Hệ điều hành để chạy chương trình là linux (CentOS)
Hệ thống có khả năng cân bằng tải dựa vào nhiều tiêu chí, bao gồm:
o Độ trễ (delay)
o Biến thiên độ trễ (jitter)
o Tỉ lệ mất gói (loss rate)
o Băng thông (bandwidth)
5
1.5 Bố cục luận văn
Chương 1: Giới thiệu
Chương 1 giới thiệu chung về hiện trạng, nhu cầu và xu hướng chọn lựa giải
thuật cân bằng tải trong hệ thống mạng. Chương này cũng trình bày mục tiêu, đối
tượng và phạm vi nghiên cứu. Cuối chương nêu tóm tắt bố cục của toàn luận văn.
Chương 2: Xây dựng giải thuật cân bằng tải
Chương 2 sẽ trình bày các khái niệm, đặc điểm, chức năng của cân bằng tải.
Cân bằng tải là sự chia sẻ công việc cho hai hay nhiều đối tượng cùng tính
năng xử lý. Đối tượng ở đây có thể là máy chủ, CPU, đường truyền internet, thiết bị
lưu trữ,…Tác vụ cân bằng tải có thể được thực hiện bởi phần cứng hoặc phần mềm
hoặc cả hai. Và tác dụng của cân bằng tải đó là:
a) Tối ưu tài nguyên (tránh quá tải)
Tất cả tài nguyên được sử dụng gần như “triệt để”. Ví dụ, nếu các kết nối
internet của doanh nghiệp được cân bằng tải thì lưu lượng được phân phối trên tất
cả các hướng, không có trạng thái “đường nghẽn, đường trống”. Tổng quát như sau:
o Gọi khối lượng công việc cần xử lý là M
o Gọi số đối tượng có thể xử lý công việc là N
o Gọi công suất xử lý công việc của đối tượng N
i
là: W
i
(với i là số thứ tự
của đối tượng)
o Khi đó, bộ cân tải sẽ tối ưu tài nguyên bằng cách chia nhỏ công việc M
thành N phần P
i
sao cho P
i
/P
i+1
= W
i
/W
i+17
c) Tăng tính dự phòng
Khi một đối tượng bị lỗi, các đối tượng khác sẽ lập tức thay thế để đảm bảo
công việc không bị gián đoạn. Giả sử một doanh nghiệp cần thuê 4 Mbps leased-
line. Họ đang cân nhắc chọn một trong hai giải pháp sau: Một là sử dụng duy nhất
một đường truyền 4 Mbps; hai là sử dụng hai đường, trong đó mỗi đường bằng 2
Mbps. Rõ ràng giải pháp thứ hai sẽ tốt hơn vì nếu được kết hợp với tính năng cân
bằng tải thì độ sẵn sàng (hay khả năng dự phòng) sẽ cao hơn so với giải pháp đầu
tiên. Tổng quát như sau:
o Gọi khối lượng công việc cần xử lý là M
o Gọi số đối tượng có thể xử lý công việc là N
o Nếu đối tượng Ni bị lỗi thì N-1 đối tượng còn lại có thể thay thế để xử lý
công việc. Đây là một đặc điểm quan trọng để bảo đảm luồng công việc
vẫn được liên tục khi có vài trong số các đối tượng bị lỗi.
d) Tăng khả năng mở rộng
Cơ chế cân bằng tải luôn cho phép bổ sung các đối tượng xử lý vào hệ thống
mà không làm ảnh hưởng đến tính năng. Ví dụ người dùng có thể bổ sung thêm hai
hay nhiều đường truyền internet vào hệ thống cân bằng tải hiện tại để phù hợp với
sự phát triển hoặc nhu cầu của công ty. Tổng quát như sau:
o Gọi khối lượng công việc cần xử lý là M
o Gọi số đối tượng có thể xử lý công việc là N
o Gọi số đối tượng có thể xử lý công việc cần bổ sung vào hệ thống là K
o Trước khi bổ sung, công việc được phân phối cho N đối tượng. Sau khi
bổ sung, công việc được thực hiện nhanh hơn vì số lượng đối tượng xử lý
công việc được tăng lên (tức N + K đối tượng). Tóm lại, nguyên lý cân
9
bằng tải vẫn sẽ thực hiện đúng chức năng của mình ngay cả khi hệ thống
được mở rộng bằng cách bổ sung một hoặc nhiều đối tượng xử lý.
2.2 Phân loại
Internet
ISP A
ISP B ISP C
Mạng LAN
X Mbps = X1 + X2 + X3
X1 X2
X3
Hình 2.3: Tổng quát về cân bằng tải kết nối (link load-balancer)
Cân bằng tải kết nối (link load-balancer) thực hiện việc phân phối băng
thông giữa các đường truyền internet hoặc giữa các đường truyền nội bộ. Loại này
thường bao gồm các chức năng sau:
a) Dự phòng kết nối (link fail-over)
Trong trường hợp tất cả các kết nối đều hoạt động tốt, lưu lượng được phân
phối trên tất cả các kết nối. Nếu có một hoặc nhiều kết nối bị lỗi thì lưu lượng tự
động dồn qua các kết nối còn lại (tạm gọi là “danh sách kết nối hoạt động tốt”).
Ngay khi kết nối lỗi nào đó được phục hồi thì thiết bị cân tải sẽ tự động bổ sung kết
nối này vào “danh sách kết nối hoạt động tốt”. Điều này đảm bảo tính dự phòng cho
các kết nối, nghĩa là nếu vài trong số các kết nối bị lỗi thì mạng vẫn có thể hoạt
động được.
11
b) Cân tải lưu lượng (traffic balancing)
Thiết bị cân tải có nhiệm vụ phân phối lưu lượng qua các kết nối. Hiện nay
có rất nhiều giải thuật cân tải để tổ chức có thể lựa chọn loại phù hợp với nhu cầu
và hiện trạng của mình. Một vài giải thuật thông dụng bao gồm round-robin, least
used, fastest response time,…
c) Nhất quán phiên giao dịch (session persistence)
Đối với các loại lưu lượng đặc biệt như SIP (VoIP), HTTPS và FTP,…
đầu “quét” lại kết nối đầu tiên của danh sách.
Gọi số gói tin cần xử lý là M.
Gọi số kết nối có thể xử lý gói tin là N.
Khi đó, bộ cân tải sẽ phân phối gói tin thứ i vào kết nối N
i%N
. Bảng 2.1 dưới
đây minh họa việc phân phối gói tin trong giải thuật round-robin.
Bảng 2.1: Cách phân phối gói tin trong giải thuật “xoay vòng” (round-robin)
Số thứ tự gói tin (M
i
)
Kết nối (N
= 3)
M1
N1
M2
N2
M3
N3
M4
N1
M5
N2
M6
N3
M7
N1
kết nối của ISP2 có trọng số bằng 3, thì danh sách sẽ như sau: ISP1 ISP1 ISP2 ISP2
ISP2. Khi đó, gói tin đầu tiên được truyền qua kết nối được định nghĩa đầu tiên
trong danh sách. Gói tin thứ hai sẽ được truyền qua kết nối thứ hai. Khi bộ cân tải
duyệt đến kết nối cuối cùng của danh sách thì bắt đầu “quét” lại kết nối đầu tiên của
danh sách.
Gọi số gói tin cần xử lý là M
Gọi số kết nối có thể xử lý gói tin là N
Gọi trọng số của kết nối N
i
là W
i
Khi đó, bộ cân tải sẽ phân phối gói tin thứ i vào kết nối như bảng sau:
14 Bảng 2. 2:Cách phân phối gói tin trong giải thuật “xoay vòng theo trọng số”
(weighted round-robin)
Số thứ tự gói tin
(với k là số thứ tự lần quét danh sách)
Kết nối
Số lần lặp
M
1*k
N
1
W
1
3
W
3
lần M
(W1+W2+W3)*k
N
3 c) Nhận xét
Ưu điểm: Bộ cân tải không phải xử lý nhiều (chỉ cần luân phiên việc truyền
gói tin qua danh sách các kết nối được thiết lập dựa vào trọng số).
Nhược điểm: Chỉ dựa vào tiêu chí băng thông để truyền dữ liệu, không dựa
vào độ trễ, độ rớt gói, biến thiên độ trễ, Do đó, giải thuật này chỉ cân tải lưu
lượng qua các kết nối mà chưa quan tâm đến chất lượng hướng kết nối. 15
2.4.3 Độ ưu tiên (Priority)
Internet
cuối danh sách?
Xét kết nối tiếp theo trong danh sách
(tức các kết nối có độ ưu tiên thấp hơn)
Truyền gói tin theo kết
nối này
Kết thúc
- Gói gin
- Danh sách các kết nối theo thứ tự
“độ ưu tiên” giảm dần
Đúng
Sai
Đúng
Sai
Truyền gói tin theo bảng
định tuyến hiện tại
Hình 2.7: Nguyên lý hoạt động của giải thuật “độ ưu tiên” (priority)
c) Nhận xét
Ưu điểm: Bộ cân tải không phải xử lý nhiều (chỉ cần “default-route” về một
hướng có độ ưu tiên cao nhất. Nếu hướng này bị lỗi thì tự động đổi “default-
route” qua hướng có độ ưu tiên thấp hơn).
Nhược điểm: Tại một thời điểm chỉ sử dụng một đường duy nhất. Giải thuật
này chưa khai thác hiệu quả tổng tài nguyên đang có.
Copyright: Tài liệu đại học ©