(Luận Văn Thạc Sĩ) Khoa Học Máy Tính Nghiên Cứu Kỹ Thuật Cân Bằng Tải Trong Điện Toán Đám Mây.pdf

1-i

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC QUỐC TẾ HỒNG BÀNG

---------------------------------------

VÕ VĂN KHANG

Tên đề tài luận văn:

NGHIÊN CỨU KỸ THUẬT CÂN BẰNG TẢI

TRONG ĐIỆN TOÁN ĐÁM MÂY

Chuyên ngành : Khoa học máy tính

Mã số chuyên ngành : 60 48 01

LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC

TS. NGUYỄN HỒNG SƠN

TP.HỒ CHÍ MINH – NĂM 2014

1-ii

CHUẨN Y CỦA HỘI ĐỒNG BẢO VỆ LUẬN VĂN

Luận văn tựa đề: Nghiên Cứu Kỹ Thuật Cân Bằng Tải Trong Điện Toán

Đám Mây được Võ Văn Khang thực hiện và nộp nhằm thoả một trong các yêu cầu

tốt nghiệp Thạc sĩ ngành Khoa Học Máy Tính.

Chủ tịch Hội đồng

GS.TSKH HOÀNG VĂN KIẾM

Cố Vấn Hiệu Trưởng Trường Đại Học

Quốc Tế Hồng Bàng

Ngày 22 tháng 09 năm 2014

Giảng viên hướng dẫn

TS. NGUYỄN HỒNG SƠN

Trưởng Khoa Công Nghệ Thông Tin

Học Viện Bưu Chính Viễn Thông

Cơ Sở TP.HCM

Ngày 22 tháng 09 năm 2014

Ngày bảo vệ luận văn, Tp.HCM, Ngày 24 tháng 08 năm 2014

Viện Đào Tạo Sau Đại Học

……………………..

i

LÝ LỊCH CÁ NHÂN

Tôi tên là: Võ Văn Khang Sinh ngày: 1982 Nơi Sinh: Long An

Tốt nghiệp THPT tại Trường THPT Vĩnh Hưng – Long An, năm 2000.

Quá trình công tác:

 Từ năm 2004 đến 2006 làm việc tại Trường dạy nghề ITEE – Tp.HCM.

 Từ năm 2006 đến nay làm việc tại Trường Trung Cấp Âu Việt – Tp.HCM.

Địa chỉ liên lạc : 331/38/37F Phan Huy Ích, P14, Q.Gò Vấp, Tp.HCM

Điện thoại : 0907.306.863 – 0963.038.079

Email : [email protected]

ii

LỜI CAM ĐOAN

Tôi cam đoan rằng luận văn này : “Nghiên Cứu Kỹ Thuật Cân Bằng Tải Trong

Điện Toán Đám Mây“ là bài nghiên cứu của chính tôi.

Ngoại trừ những tài liệu tham khảo được trích dẫn trong luận văn này, tôi cam

đoan rằng toàn phần hay những phần nhỏ của luận văn này chưa từng được công bố

hay được sử dụng để nhận bằng cấp ở những nơi khác.

Không có sản phẩm nghiên cứu nào của người khác được sử dụng trong luận văn

này mà không được trích dẫn theo đúng quy định.

Luận văn này chưa bao giờ được nộp để nhận bất kỳ bằng cấp nào tại các trường

đại học hoặc cơ sở đào tạo khác.

Tp.HCM, ngày 08 tháng 07 năm 2014

Tác giả luận văn

Võ Văn Khang

iii

LỜI CẢM ƠN

Trong suốt quá trình học tập, nghiên cứu và thực hiện đề tài luận văn thạc

sĩ, ngoài những cố gắng và nỗ lực của bản thân, tôi đã nhận được sự hướng dẫn,

giúp đỡ quý báu của quý thầy cô, cùng với sự động viên, khích lệ và ủng hộ của các

đồng nghiệp, bạn bè và gia đình. Với lòng kính trọng và biết ơn sâu sắc tôi xin được

bày tỏ lời cảm ơn chân thành tới:

Ban giám hiệu, Viện đào tạo sau đại học, đã tạo mọi điều kiện thuận lợi giúp

đỡ tôi trong quá trình học tập và hoàn thành luận văn.

Tôi xin chân thành cảm ơn tiến sĩ Nguyễn Hồng Sơn, người thầy kính mến

đã hết lòng giúp đỡ, dạy bảo, động viên và tạo mọi điều kiện thuận lợi cho tôi trong

suốt quá trình học tập và hoàn thành luận văn tốt nghiệp. Tôi xin gửi lời tri ân đến

thầy, đối với những điều mà thầy đã dành cho tôi trong suốt thời gian qua.

Tôi xin chân thành biết ơn toàn thể quý thầy cô Khoa công nghệ thông tin,

Viện đào tạo sau đại học, Trường đại học quốc tế Hồng Bàng đã tận tình

truyền đạt những bài học cũng như những kiến thức quý báu trong quá trình học tập

và thực hiện đề tài này.

Xin chân thành cảm ơn quý thầy cô trong hội đồng chấm luận văn đã cho tôi

những đóng góp quý báu để hoàn chỉnh luận văn này.

Tôi xin bày tỏ lòng biết ơn đến lãnh đạo Trường Trung Cấp Âu Việt, đặc

biệt là anh em trong khoa CNTT và tất cả các đồng nghiệp đã hỗ trợ và tạo điều

kiện tốt nhất để tôi học tập và nghiên cứu đề tài một cách tốt nhất.

Tôi xin chân thành cảm ơn mọi người trong gia đình tôi, đã tạo điều kiện,

động viên khích lệ tôi trong những lúc khó khăn để tôi học tập và thực hiện đề tài.

Mặc dù đã cố gắng hết sức, song do thời gian và kinh nghiệm nghiên cứu

khoa học còn hạn chế nên không thể tránh khỏi những thiếu sót. Tôi rất mong nhận

được sự góp ý của quý thầy cô cùng bạn bè đồng nghiệp để kiến thức của mình

ngày một hoàn thiện hơn.

Tp.Hồ Chí Minh, tháng 7 năm 2014

Người thực hiện luận văn

Võ Văn Khang

iv

TÓM TẮT

Điện toán đám mây là xu hướng hội tụ của nhiều thành tựu về nghiên cứu

phát triển và ứng dụng công nghệ mới; các quan điểm về ứng dụng công nghệ thông

tin hiện nay trên thế giới. Tầm quan trọng của nó đã được nhấn mạnh trong một

báo cáo gần đây từ trường đại học Berkeley: “Điện toán đám mây, giấc mơ lâu

nay của máy tính như là một tiện ích có khả năng chuyển đổi một phần lớn ngành

công nghiệp công nghệ thông tin, làm mềm thậm chí còn hấp dẫn hơn như một

dịch vụ” [16].

Một kỹ thuật góp phần quan trọng giúp điện toán đám mây được triển khai

thành công đó là cân bằng tải. Nó giải quyết được các vấn đề về chiến lược phân

bổ, sự tận dụng tài nguyên tính toán một cách có hiệu quả. Khi nói đến cân bằng

tải người ta thường nghĩ đến làm thế nào phân phối khối lượng công việc giữa các

nút tính toán sau cho công bằng, ít gây ra sự lãng phí và tận dụng tài nguyên hiệu

quả nhất. Trong mô hình điện toán đám mây, thành phần Broker chịu trách nhiệm

trung gian đàm phán giữa nhà cung cấp SaaS và nhà cung cấp dịch vụ đám mây.

Nó đại diện cho nhà cung cấp SaaS tìm kiếm nhà cung cấp dịch vụ đám mây phù

hợp và đảm nhiệm đàm phán trực tuyến để cấp phát nguồn tài nguyên hay dịch vụ

có thể đáp ứng yêu cầu QoS của ứng dụng. Với vai trò điều phối, Broker thực hiện

các chiến lược cân bằng tải để phân phối yêu cầu xử lý của người dùng đến nguồn

tài nguyên tính toán sau cho có hiệu quả nhất. Nhằm nghiên cứu các kỹ thuật cân

bằng tải đang được áp dụng hiện nay trong điện toán đám mây, luận văn sẽ thực

hiện các thuật toán cân bằng tải tại thành phần Broker. Muốn làm được điều

này cần một môi trường có thể mô hình và mô phỏng đầy đủ các thành phần của

điện toán đám mây như là Datacenter, máy ảo, Broker và các chính sách cung cấp

nguồn tài nguyên. Để vượt qua thách thức đó tác giả nghiên cứu môi trường mô

hình và mô phỏng điện toán đám mây CloudSim để thực nghiệm. Dựa trên kết quả

đạt được tác giả sẽ phân tích, đánh giá hiệu quả của các thuật toán cân bằng tải

hiện nay; đồng thời phát hiện hạn chế từ đó có những đề xuất thuật toán cân bằng

tải cải tiến.

v

ABSTRACT

Cloud computing is the convergence of several trends achievements in

research, development and application of new technologies; views on the application

of information technology in the world today. Its importance was highlighted in a

recent report from the University of Berkeley: "Cloud computing, long-held dream

of the computer as a utility capable of converting a large part industry information

technology, soften even more attractive as a service "[16].

An important contribution to the technical help of cloud computing is that

success is implementing load balancing. It solves the problem of allocation

strategies, the advantage of the computing resources efficiently. When thinking

about load balancing people often think how to distribute the workload among the

compute nodes after the fair, cause less waste and make the most efficient use of

resources. In the cloud model, Broker component responsible mediated negotiations

between SaaS vendors and cloud service providers. It represents SaaS providers

looking for cloud service providers and undertake appropriate online negotiation to

allocate resources or services can meet the QoS requirements of the application.

With a coordinating role, Broker perform load balancing strategy for distributed

processing requirements of users to calculate the following resources for the most

effective. In order to study the load-balancing techniques are being applied today in

cloud computing, this Thesis will perform load balancing algorithms in Broker

components. To achieve this requires an environment that can model and simulate

the full range of components of cloud computing as Datacenter, VM, Broker and

provide policy resources. To overcome that challenge study author and

environmental simulation model cloud CloudSim to experiment. Based on the

results the author will analyze and evaluate the effectiveness of the load balancing

algorithm present; simultaneous detection thereby limiting the proposed load

balancing algorithm improvements.

vi

MỤC LỤC

TRANG PHỤ BÌA

LÝ LỊCH CÁ NHÂN ....................................................................................................... i

LỜI CAM ĐOAN ........................................................................................................... ii

LỜI CẢM ƠN ............................................................................................................... iii

TÓM TẮT ...................................................................................................................... iv

ABSTRACT .................................................................................................................... v

MỤC LỤC ..................................................................................................................... vi

DANH SÁCH HÌNH VẼ ............................................................................................. ix

DANH SÁCH BẢNG ................................................................................................... xi

DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT ............................................. xiii

CHƯƠNG 1: GIỚI THIỆU ......................................................................................... 1

1.1 Lý do chọn đề tài ........................................................................................................ 1

1.2 Công trình nghiên cứu gần đây về cân bằng tải điện toán đám mây ................. 3

1.2.1 Cải thiện thời gian đáp ứng: ............................................................................. 3

1.2.2 Vấn đề tiêu thụ năng lượng .............................................................................. 3

1.2.3 Vấn đề di trú máy ảo ......................................................................................... 4

1.3 Mục tiêu luận văn .................................................................................................... 4

1.4 Tổ chức luận văn ..................................................................................................... 4

CHƯƠNG 2: CÂN BẰNG TẢI TRONG ĐIỆN TOÁN ĐÁM MÂY ................... 6

2.1 Tổng quan về điện toán đám mây ............................................................................. 6

2.2 Tổng quan về cân bằng tải trong điện toán đám mây ......................................... 7

2.2.1 Giới thiệu kỹ thuật cân bằng tải ....................................................................... 7

2.2.2 Mục đích cân bằng tải ....................................................................................... 8

2.2.3 Cân bằng tải trong điện toán đám mây ............................................................ 9

2.2.4 Đo lường cân bằng tải trong điện toán đám mây .......................................... 10

2.3 Các thuật toán cân bằng tải đang được ứng dụng hiện nay ............................. 11

2.3.1 Cân bằng tải tĩnh ............................................................................................. 13

2.3.2 Cân bằng tải động ........................................................................................... 14

vii

2.3.3 Vấn đề trong cân bằng tải động ...................................................................... 15

2.4 So sánh giữa kỹ thuật cân bằng tĩnh và cân bằng tải động[11] ........................ 16

2.4.1 Bản chất ........................................................................................................... 16

2.4.2 Liên quan phí tổn ............................................................................................ 16

2.4.3 Tận dụng tài nguyên ....................................................................................... 17

2.4.4 “Thrashing” hay tiến trình “Dumping” ........................................................ 17

2.4.5 Trạng thái “Woggling” ................................................................................... 17

2.4.6 Khả năng tiên đoán ......................................................................................... 18

2.4.7 Khả năng thích ứng ........................................................................................ 18

2.4.8 Độ tin cậy ......................................................................................................... 18

2.4.9 Thời gian đáp ứng ........................................................................................... 18

2.4.10 Khả năng ổn định .......................................................................................... 18

2.4.11 Liên quan sự phức tạp .................................................................................. 19

2.4.12 Chi phí phát triển........................................................................................... 19

2.5 Kết luận ................................................................................................................... 20

CHƯƠNG 3: CÁC THUẬT TOÁN CÂN BẰNG TẢI TIÊU BIỂU ..................... 21

3.1 Cân bằng tải trong điện toán đám mây ................................................................. 21

3.2 Thuật toán Round-Robin ....................................................................................... 22

3.3 Thuật toán Weighted Round-Robin ....................................................................... 22

3.4 Thuật toán Active Monitoring Load Balancer ...................................................... 23

3.4.1 Mô tả thuật toán [7],[24] .................................................................................. 23

3.4.2 Thuật toán ......................................................................................................... 23

3.4.3 Đánh giá .......................................................................................................... 24

CHƯƠNG 4: DỀ XUẤT THUẬT TOÁN CÂN BẰNG TẢI CẢI TIẾN ............ 25

4.1 Giới thiệu ................................................................................................................. 25

4.2 Mô hình cân bằng tải trong điện toán đám mây ................................................ 29

4.3 Đề xuất thuật toán cải tiến ....................................................................................... 30

4.3.1 Ý tưởng cải tiến ................................................................................................ 30

4.3.2 Phân tích hệ thống .......................................................................................... 30

4.3.3 Cơ sở tính toán cho giải thuật cải tiến .............................................................. 35

4.3.4 Thiết kế thuật toán ........................................................................................... 38