ĐẠI HỌC QUỐC GIA TP. HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA
--------------------

TRẦN HOÀNG VINH

LẤY MẪU DỮ LIỆU ĐẦU VÀO ĐỂ CẢI THIỆN GIẢI THUẬT
TÔ MÀU CHO MẠNG LƯỚI CDNS
Chuyên ngành : Khoa Học Máy Tính
Mã số: 8.48.01.01

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 7 năm 2023


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA –ĐHQG -HCM
Cán bộ hướng dẫn khoa học : PGS . TS. Thoại Nam

Cán bộ chấm nhận xét 1 : TS. Nguyễn Lê Duy Lai

Cán bộ chấm nhận xét 2 : PGS. TS. Trần Công Hùng
Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG Tp. HCM
ngày 13 tháng 7 năm 2023
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
1. PGS. TS Trần Văn Hoài ...............- Chủ tịch hội đồng
2. TS. Lê Thành Sách .......................- Thư ký
3. TS. Nguyễn Lê Duy Lai ...............- Phản biện 1
4. PGS. TS. Trần Công Hùng ...........- Phản biện 2
5. PGS. TS. Lê Trung Quân .............- Ủy Viên

Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyên
ngành sau khi luận văn đã được sửa chữa (nếu có).
CHỦ TỊCH HỘI ĐỒNG

TRƯỞNG KHOA
KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH


ĐẠI HỌC QUỐC GIA TP.HCM
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc
TRƯỜNG ĐẠI HỌC BÁCH KHOA
Độc lập - Tự do - Hạnh phúc

NHIỆM VỤ LUẬN VĂN THẠC SĨ

Họ tên học viên: Trần Hoàng Vinh

MSHV: 1970135

Ngày, tháng, năm sinh: 27/03/1996

Nơi sinh: TP. Hồ Chí Minh

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

Mã số : 8480101

I. TÊN ĐỀ TÀI : Lấy mẫu dữ liệu đầu vào để cải thiện giải thuật tô màu cho mạng
lưới CDN / Sampling input data to improve coloring algorithm for Content
Delivery Network.

II. NHIỆM VỤ VÀ NỘI DUNG: Thực hiện nghiên cứu và đánh giá việc cải thiện giải
thuật tô màu cho mạng CDNs thông qua việc lấy mẫu dữ liệu đầu vào.
III. NGÀY GIAO NHIỆM VỤ : 06/02/2023
IV. NGÀY HOÀN THÀNH NHIỆM VỤ: 11/06/2023
V. CÁN BỘ HƯỚNG DẪN: PGS.TS Thoại Nam

Tp. HCM, ngày tháng năm 2023
CÁN BỘ HƯỚNG DẪN
(Họ tên và chữ ký)

HỘI ĐỒNG NGÀNH

(Họ tên và chữ ký)

TRƯỞNG KHOA
KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH

(Họ tên và chữ ký)

i


LỜI CẢM ƠN
Tôi xin chân thành gửi lời cảm ơn đến thầy Thoại Nam – Phó Giáo sư Tiến
sĩ của trường đại học Bách Khoa Thành phố Hồ Chí Minh. Thầy đã tận tình hướng
dẫn, chỉ bảo tơi và giải đáp thắc mắc trong suốt quá trình thực hiện đề tài. Bên
cạnh đó, xin cảm ơn thạc sĩ La Hồng Lộc, người đã hỗ trợ tôi chạy lại giải thuật
tô màu cho mạng CDNs mơ phỏng. Ngồi ra, tơi cũng gửi lời biết ơn chân thành
tới tất cả các quý Thầy, Cơ trong khoa Khoa học Máy Tính đã nhiệt tình giảng
dạy, truyền đạt kiến thức cho tơi trong suốt q trình học tập tại trường.


Trân Trọng
TP. Hồ Chí Minh, ngày 13 tháng 7 năm 2023
Trần Hoàng Vinh

ii


TÓM TẮT LUẬN VĂN
Cùng với sự tăng trưởng về số lượng nội dung trên mạng Internet như hiện
nay, việc truyền tải nội dung tới người dùng ở khắp nơi trên thế giới cần sự hỗ
trợ của mạng phân phối nội dung (Content Delivery Networks). Nhằm cải thiện
hiệu suất của mạng và tối ưu lưu lượng truyền tải trong mạng, một số phương
pháp được đưa ra, trong đó giải thuật tơ màu cho mạng CDNs mang lại kết quả
khả quan nhất. Tuy nhiên, độ phưc tạp của giải thuật phụ thuộc phần lớn vào số
lượng yêu cầu của người dùng và số lượng nội dung. Bên cạnh đó, chi phí để
truyền tải nội dung về trung tâm để thực hiện tính tốn lại giải thuật tơ màu cũng
là một chi phí không hề nhỏ và thời gian để chạy giải thuật cũng là một vấn đề
cần xem xét. Trước những vấn đề đó, luận văn đưa ra hướng giải quyết cho việc
giảm độ phức tạp của giải thuật tô màu bằng cách lấy mẫu. Việc lấy mẫu cũng
được chia làm 2 bài toán nhỏ, lấy mẫu tập trung và lấy mẫu phân tán. Trong đó
lấy mẫu tập trung nhằm giải quyết vấn đề độ phức tạp của giải thuật tô màu và
lấy mẫu phân tán giúp giảm tải chi phí đẩy dữ liệu về trung tâm để xử lý. Cùng
với các chứng minh về lý thuyết và các kết quả thực nghiệm, luận văn đã cho thấy
được tính cần thiết của việc lấy mẫu và đưa ra công thức để đánh giá độ tương
đồng của tập dữ liệu trước và sau khi lấy mẫu. Từ đó, đóng góp một phần vào
việc tối ưu mạng phân phối nội dung thông qua giải thuật tô màu.

iii



ABSTRACT
Along with the growth in the number of content on the Internet as it is
today, the delivery of content to users around the world needs the support of
content distribution networks (Content Delivery Networks). In order to improve
network performance and optimize traffic transmission in the network, some
methods are proposed, in which the coloring algorithm for CDNs networks brings
the most promising results. However, the complexity of the algorithm depends
largely on the number of user requests and the number of content. In addition, the
cost of transmitting content to the center to perform recalculation of the coloring
algorithm is also a significant cost and the time to run the algorithm is also an
issue to consider. Facing these problems, the thesis proposes a solution to reduce
the complexity of the coloring algorithm by sampling. Sampling is also divided
into 2 small problems, centralized sampling and distributed sampling. In which
centralized sampling aims to solve the problem of complexity of coloring
algorithm and distributed sampling helps reduce data push cost to center for
processing. Along with theoretical proofs and experimental results, the thesis has
shown the necessity of sampling and gives a formula to evaluate the similarity of
data sets before and after sampling. From there, contributing a part to optimizing
content distribution networks through coloring algorithms.

iv


LỜI CAM ĐOAN
Tôi xin cam đoan rằng tất cả những thơng tin và kết quả được trình bày
trong luận văn này ngoài việc tham khảo các nguồn tài liệu đã được ghi đầy đủ
trong phần phụ lục các tài liệu tham khảo, thì đều cho chính tơi thực hiện. Khơng
có phần nội dung nào được sao chép từ các đề tài thực tập tốt nghiệp, luận văn
đại học của trường này hay trường khác. Nếu có bất kỳ sai phạm hay gian lận

nào, tơi xin hồn tồn chịu trách nhiệm trước Ban Chủ Nhiệm Khoa và Ban Giám
Hiệu Nhà Trường.
Người cam đoan

Trần Hoàng Vinh

v


MỤC LỤC
NHIỆM VỤ LUẬN VĂN THẠC SĨ ......................................................... i
LỜI CẢM ƠN ...........................................................................................ii
TÓM TẮT LUẬN VĂN ......................................................................... iii
ABSTRACT..............................................................................................iv
LỜI CAM ĐOAN ...................................................................................... v
CHƯƠNG 1: TỔNG QUAN VỀ ĐỀ TÀI ............................................... 1
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT ........................................................ 4
2.1. Tổng quan về mạng CDNs ............................................................... 4
2.2. Phương pháp lấy mẫu ..................................................................... 12
CHƯƠNG 3: BÀI TOÁN LẤY MẪU TẬP TRUNG TRONG MẠNG
CDNS........................................................................................................ 19
3.1. Phân tích giải thuật tơ màu trong CDNs ........................................ 19
3.2. Bài toán lấy mẫu tập trung trong mạng CDNs ............................... 21
CHƯƠNG 4: LẤY MẪU PHÂN TÁN CHO GIẢI THUẬT TÔ MÀU
TRONG CDNS ........................................................................................ 24
4.1. Giải thuật lấy mẫu phân tán trong mạng CDNs ............................. 24
4.2. Cơng thức tính độ tương đồng ....................................................... 26
CHƯƠNG 5: THỰC NGHIỆM............................................................. 29
5.1. Hệ thống, dữ liệu và công cụ thực nghiệm .................................... 29
5.2. Kết quả thực nghiệm ...................................................................... 32

CHƯƠNG 6: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN..................... 40
6.1. Kết luận .......................................................................................... 40
6.2. Hướng phát triển ............................................................................ 41
vi


TÀI LIỆU THAM KHẢO...................................................................... 42
PHẦN LÝ LỊCH TRÍCH NGANG ....................................................... 44

vii


CHƯƠNG 1: TỔNG QUAN VỀ ĐỀ TÀI
Ngày nay, Internet gần như là công cụ quan trọng trong cuộc sống thường
ngày. Nhờ Internet, chúng ta có thể tiếp cận với những nội dung mới thường
xuyên thông qua các trang web, mạng xã hội, giúp con người dễ dàng kết nối với
nhau. Tính đến ngày 31/12/2021, đã có khoảng 5,385,798,406 người dùng
Internet trên toàn cầu, chiếm khoảng 67,9% dân số thế giới [1]. Theo trang web
[2], tính đến thời điểm hiện tại đã có hơn 160 triệu website đang hoạt động trên
Internet. Thơng qua đó, chúng ta thấy được sự phức tạp của mạng lưới Internet
hiện nay và nguyên nhân chính dẫn đến sự tắt nghẽn mạng lưới truyền tải trên
Internet. Kỹ thuật sử dụng mạng phân phối nội dung (Content Delivery Networks
– CDN) được đề xuất nhằm giải quyết vấn đề trên. Người dùng ở bất cứ vị trí địa
lý nào trên cũng có thể tiếp cận được nội dung ở cách xa họ hơn nửa vịng trái đất
thơng qua các Edge Server mà không gặp trở ngại về đường truyền. Nói đơn giản,
một người dùng ở Việt Nam muốn truy cập 1 nội dung được đặt ở máy chủ bên
Mỹ sẽ tốn rất nhiều thời gian hơn so với việc truy cập nội dung đó được lưu ở
máy chủ đặt ở Singapore. Điều này giúp tăng tỉ lệ truy cập của nội dung đó cũng
như trải nghiệm của người dùng. Tuy nhiên, số lượng nội dung sinh ra hằng ngày
càng nhiều và độ phổ biến của nội dung thay đổi nhanh chóng theo giờ, nhưng

phần cứng trên các Edge Server thì có giới hạn. Vì thế, tác giả Nakajima [3] đã
đề xuất chiến lược Cooperative Caching kết hợp với giải thuật tơ màu để các Edge
Server có thể bắt kịp với sự thay đổi của nội dung. Tuy nhiên, với số lượng nội
dung ngày càng nở rộng, giải thuật tô màu cho mạng CDNs sẽ có độ phức tạp
càng lớn, dẫn đến việc tăng thời gian tính tốn cũng như chi phí trong mạng
CDNs. Mục tiêu chính của luận văn là cải thiện thời gian xử lý và chi phí đường
truyền trong mạng CDNs thông qua việc lấy mẫu. Cụ thể, đề tài sẽ tập trung vào
hai bài toán lấy mẫu chính là lấy mẫu tập trung và lấy mẫu phân tán. Qua đó, đưa
ra một cơng thức về tính tương đồng của tập dữ liệu trước và sau khi lấy mẫu trên

1


cả hai bài toán này. Luận văn cũng thử nghiệm trên tập dữ liệu thực tế được trích
suất từ một ISP lớn của Việt Nam.
Mục tiêu đề tài:
1. Chia nhỏ bài toán lấy mẫu dữ liệu đầu vào cho mạng CDNs thành
hai hướng tiếp cận chính: Lấy mẫu tập trung và lấy mẫu phân tán.
2. Đưa ra công thức đánh giá tính tương đồng giữa kết quả của giải
thuật tơ màu trước vào sau khi lấy mẫu.
3. Thực nghiệm việc lấy mẫu trên tập dữ liệu thực tế và đánh giá
kết quả thông qua mạng CDN mô phỏng.
Đối tượng và phạm vi nghiên cứu:
Trong luận văn này, mạng CDN sẽ được mô phỏng lại bưởi công cụ
Mininet. Đầu vào của mạng sẽ là dữ liệu yêu cầu của người dùng theo thời gian
được trích suất từ một ISP lớn của Việt Nam trong ngày 6/12/2018. Tập dữ liệu
này được chia thành 24 khoảng thời gian với mỗi khoảng thời gian tương ứng với
1 tiếng trong ngày. Phạm vi nghiên cứu của luân văn sẽ tập trung vào việc lấy
mẫu của dữ liệu đầu vào, đánh giá sự tương đồng của đầu ra giải thuật tô màu
trước và sau lấy mẫu.

Phương pháp:
Đề tài sử dụng kỹ thuật lấy mẫu (Data Sampling) để giảm tải khối lượng
dữ liệu, từ đó làm giảm độ phức tạp của giải thuật tô màu. Dữ liệu này sẽ được
chạy trong mạng CDN mô phỏng để sinh ra tập số để tô màu nội dung tương ứng.
Tập số này là kết quả chính nhằm đánh giá tính tương đồng giữa kết quả trước và
sau lấy mẫu thông qua công thức phát triển từ giải thuật đánh giá tính tương động
Jaccard.
Cấu trúc luận văn:
Chương 1 sẽ giới thiệu về đề tài, mục tiêu của nghiên cứu và tóm tắt luận
văn. Chương 2 sẽ tập trung mô tả cơ sở lý thuyết, các định nghĩa, các nghiên cứu
liên quan về mạng CDNs và các kỹ thuật lấy mẫu. Chương 3 và 4 sẽ mơ tả bài
tốn lấy mẫu tập trung và phân tán trong mạng CDNs và công thức về độ tương
2


đồng giữa tập dữ liệu lấy mẫu và tập dữ liệu ban đầu. Chương 5 sẽ thực nghiệm
trên tập dữ liệu thực tế và đánh giá kết quả đạt được trong chương 6. Từ đó, đưa
ra kết luận và hướng phát triển cho đề tài này.

3


CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
2.1. Tổng quan về mạng CDNs
Cơ sở lý thuyết và việc mô phỏng mạng CDNs đã được mô tả trong các bài
báo [3, 4, 5].Cụ thể như sau:
2.1.1. Mạng CDNs
Mạng CDNs là một mạng lưới bao gồm nhiều máy chủ hỗ trợ lẫn nhau để
cung cấp nội dung đến người dùng từ nhiều khu vực, vị trí địa lý khác nhau. Mạng
lưới CDNs này đóng góp cải thiện băng thơng tiêu thụ và thời gian người dùng

nhận được nội dung yêu cầu. Hiện nay, mạng lưới CDNs được áp dụng khá phổ
biến, đặc biệt là các nhà cung cấp dịch vu Video-on-Demand. Vì được đặt ở nhiều
vùng địa lý khác nhau, người dùng ở bất kỳ nơi nào cũng có thể nhận được nội
dung yêu cầu thông qua máy chủ gần nhất. Điều này giúp tăng trải nghiệm của
người dung và giảm thiểu thời gian phản hồi của máy chủ gốc (Orgin Server).
Một mạng lưới CDNs bao gồm các thành phần sau:
● Origin Server: Là máy chủ gốc chứa toàn bộ nội dung.
● Edge Server (Cache server): Là các máy chủ đặt tại các vị trí địa lý
khác nhau để phục vụ người dùng. Các máy chủ này có nhiệm vụ chính là lưu trữ
một bản sao của nội dung từ máy chủ gốc và phân phối nội dung đó tới người
dùng.
Điểm mạnh của mạng CDN là cải thiện được trải nghiệm của người dùng
cuối. Điều này rất quan trọng đối với các trang thương mạng điện tử, truyền hình
hay trị chơi trực tuyến. Khi người dùng truy cập vào một trang web, yêu cầu của
họ sẽ được gửi đến Edge Server có vị trí địa lý gần nhất. Nếu nội dung mà người
dùng yêu cầu khơng có, Edge Server sẽ gửi u cầu tới các Edge Server khác
trong mạng lưới hoặc về Orgin Server để lấy nội dung mà người dùng yêu cầu.
Sau đó lưu trữ một bản sao của nội dung đó lên bộ lưu trữ của chính nó để phục
vụ cho các yêu cầu sau đó của người dùng đó hoặc người dùng khác. Bên cạnh
4


đó, CDN giúp phân phối tải trọng trên nhiều máy chủ. Với một dịch vụ trong
mạng Internet, nếu chỉ được dựng trên một máy chủ đơn lẻ, số lượng yêu cầu cho
dich vụ đó sẽ bị giới hạn. Nếu vượt qua giới hạn này có thể gây ra áp lực lớn cho
máy chủ đó, dẫn đến quá tải ảnh hưởng tới dịch vụ. Nhờ vào việc phân phối tải
trọng trên nhiều máy chủ của mạng CDN, dịch vụ đó có thể tiếp nhận nhiều yêu
cầu hơn, khả năng chịu tải cao hơn. Một điểm mạnh khác của mạng CDN là khả
năng mở rộng. Với khả năng mở rộng linh hoạt, thêm các nút Edge Server và
nâng cấp hệ thống dễ dàng để đáp ứng lưu lượng truy cập ngày càng tăng của hệ

thống.
Bên cạnh những điểm mạnh trên, mạng CDNs cũng có một vài điểm yếu
cần được cải thiện và chú ý. Thứ nhất là về chi phí, để xây dừng và vận hành một
mang CDNs địi hỏi phải có chi phí đầu tư lớn. Bên cạnh đó việc phân phối và
quản lý mạng CDN có thể trở nên rất phức tạp. Đặc biệt đối với các mạng có số
lượng Edge Server lớn. Thứ hai là giới hạn về phần cứng, bên cạnh về khả năng
xử lý, khả năng lưu trữ trên các Edge Server là một giới hạn của mạng CDNs.
Việc lưu trữ nội dung trên các Edge Server sẽ bị giới hạn bởi khả năng lưu trữ vật
lý của máy chủ [3]. Thứ ba là khả năng routing trong mạng CDNs, nếu khơng có
bảng phân phối đường đi hợp lý, lưu lượng trong mạng CDNs có thể trở nên rất
lớn. Điều này ảnh hưởng trực tiếp để hiệu suất của mạng.
Để khắc phục được điểm yếu về giới hạn tài nguyên và việc routing trong
mạng CDN, Nakajima và cộng sự [3] đã đưa ra giải thuật Caching dựa theo màu
và giải thuật định tuyến dựa theo màu nhầm tối ưu việc lưu trữ trên các Edge
Server và đường đi ngắn nhất để lấy được nội dung trong mạng CDNs. Phương
pháp này cho phép các Edge Server kết hợp với nhau để tăng tỉ lệ hit cho mạng
CDNs thay vì hoạt động riêng ở từng khu vực địa lý. Cụ thể về giải thuật sẽ được
trình bày trong các mục tiếp theo

5


2.1.2. Giải thuật Caching dựa theo màu (Color-based Caching
Algorithm)
Mục đích chính của giải thuật Caching dựa theo màu trong mạng CDNs là
kết hợp các Edge Server để tăng dung lượng lưu trữ về mặt vật lý và tổ chức lại
chiến lược lưu trữ bản sao một cách hợp lý. Cụ thể, giải thuật này là sự kết hợp
giữa Cooperative Caching và Hybrid Caching. Cooperative Caching là phương
pháp kết hợp các Cache Server nhằm tăng không gian lưu trữ. Hybrid Caching
cho phép Edge Server chia không gian lưu trữ làm hai phần. Phần thứ nhất sử

dụng Least Frequently Used (LFU) để lưu trữ nội dung phổ biến để tăng tỷ lệ truy
cập, trong khi phần còn lại sử dụng First In Frist Out để lưu trữ các nội dung gần
nhất để theo dõi những thay đổi về mức độ phổ biến của nội dung. Việc kết hợp
hai chiến lược này vừa giúp tăng không gian lưu trữ cũng như đáp ứng được sự
thay đổi nhanh chóng của nội dung phổ biến.
Vấn đề đặt ra là chiến lược Hybrid Caching không hỗ trợ cho Cooperative
Caching [6]. Nếu khơng có sự kết hợp của các Edge Server khác thì có thể dẫn
đến việc lưu trữ các nội dung không phổ biến, làm giảm hiệu quả việc sử dụng
không gian lưu trữ trên các Edge Server. Tuy nhiên, giải thuật Caching dựa theo
màu đã kết hợp thành công hai ưu điểm của hai chiến lược này bằng các thẻ màu.
Trong giải thuật này, các thẻ màu sẽ được gán cho các Edge Server và các nội
dung. Nội dung nào có cùng màu với Edge Server thì sẽ được lưu trên Edge Server
đó. Với phương pháp này, các Edge Server có cùng màu sẽ tăng khơng gian lưu
trữ các nội dung phổ biến. Ngồi ra để tăng tỷ lệ truy cập của các Edge Server,
nội dung càng phổ biến sẽ được gán bởi nhiều thẻ màu. Điều này đồng nghĩa với
việc nội dung đó sẽ được lưu trữ trên nhiều Edge Server khác nhau. Ngoài ra, với
chiến lược Hybrid Caching, các Edge Server sẽ được chia làm hai không gian lưu
trữ riêng biệt. Không gian đầu tiên sử dụng phương pháp Least Frequently Used
(LFU) để lưu trữ các nội dung được đánh màu trùng với Edge Server. Khơng gian
cịn lại sử dụng phương pháp Least Recently Used (LRU) cải tiến nhằm lưu trữ
6


bất kỳ nội dung không trùng màu với Edge Server. Phương pháp LRU cải tiến [7]
này cho tỉ lệ truy cập tốt hơn phương pháp LRU [8].

Hình 1. Nội dung được đánh màu và lưu trữ trên các Edge Server được tơ màu [3]

Hình 2. Chiến lược Hybrid Caching trên Edge Server [3]


a) Đánh màu Edge Server
Mỗi Edge Server trong mạng lưới được xem như một nút trong đồ thị. Khi
này, các Edge Server sẽ được tô màu bằng giải thuật nổi tiếng của Welsh-Powell
– giải thuật tô màu độ thị bằng cách sử dụng số lượng màu ít nhất. Tuy nhiên,
thuật tốn đã được cải tiến để tơ chính xác N màu cho tất cả các Edge Server
trong mạng. Giả sử bài toán cho 4 màu (đỏ, lục, lam, vàng) để tơ cho tồn bộ các
Edge Server trong mạng, giải thuật WP cải tiến sẽ phân bố 4 màu có tỉ lệ xắp xỉ
nhau. Chi tiết về thuật tốn được mô tả trong bài báo [4].
7


b) Đánh màu nội dung
Tùy vào mức độ phổ biến của nội dung mà nội dung đó có thể có nhiều
nhất N màu. Khi này độ phổ biến của nội dung sẽ được thể hiện qua số lượng
màu mà nội dung đó được gán. Một nội dung được biểu diễn bằng N-bit vectơ,
trong đó 0 có nghĩa là khơng có màu và 1 có nghĩa là được đánh màu. Tương tự
như đánh màu Edge Server, chúng ta cũng có 4 màu (đỏ, lục, lam, vàng). Như
vậy độ phổ biến của nội dung cũng sẽ được chia làm 5 lớp. Lớp thứ nhất với tất
cả các bit là 0, lớp thứ 2 gồm 3 bit 0 và 1 bit 1, lớp thứ 3 gồm 2 bit 0 và 2 bit 1,
lớp thứ 4 gồm 1 bit 0 và 3 bit 1, và lớp cuối cùng gồm 4 bit 1.
Như vậy, việc đánh màu nội dung sẽ phụ thuộc vào độ phổ biến của nội
dung đó. Bài tốn đặt ra là làm sao để có thể biết được nội dung đó phổ biến hay
không? Yếu tố này phụ thuộc vào yêu cầu của người dùng, người dùng yêu cầu
nội dung đó càng nhiều thì nội dung đó càng phổ biến. Trong mỗi Edge Server,
khi nhận được bất kỳ yêu cầu từ người dùng, máy chủ đều sẽ lưu lại trong Access
Log của mình theo trình tự thời gian. Như vậy, chỉ cần tập hợp các Access Log
từ các Cache Server để tính tốn độ phổ biến của nội dung thơng qua tần suất yêu
cầu của nội dung đó và sắp xếp theo thứ tự số lượng yêu cầu từ cao đến thấp. Nội
dung phổ biến nhất sẽ có thứ hạng đầu tiên và nội dung được u cầu ít nhất sẽ
có thứ hạng cuối cùng. Sau đó nội dung sẽ được phân bố vào các lớp phổ biến

tương ứng. Như bảng 1, nội dung từ 1 đến 22 sẽ được đánh 4 màu, nội dung từ
23 – 25 sẽ được đánh 3 màu, nội dung có hạng từ 26 – 47 sẽ được đánh 2 màu,
nội dung có hạng từ 48 – 305 sẽ được đánh 1 màu và nội dung có hạng 306 trở
về sau sẽ không được đánh màu. Một tập số như vậy sẽ được gọi là Separator
Ranks, nhằm phân loại mức độ phổ biến của nội dung trong giải thuật tô màu.

8


Độ phổ biến
Cao

Hạng của
nội dung
1 – 22

Số màu
4

Cao – vừa

23 – 25

3

Vừa

26 – 47

2


Vừa – thấp

48 – 305

1

306 -

0

Thấp

Đỏ
1
1
1
1
0
1
1
1
0
0
0
1
0
0
0
0


Vectơ nhị phân
Lục
Lam
1
1
1
1
1
0
0
1
1
1
1
0
0
1
0
0
1
1
1
0
0
1
0
0
1
0

0
1
0
0
0
0

Vàng
1
0
1
1
1
0
0
1
0
1
1
0
0
0
1
0

Bảng 1. Bảng ánh xạ độ phổ biến và thẻ màu trong trường hợp 4 màu [4]

Như vậy, một vấn đề mới làm sao tìm được tập hợp Separator Ranks phù
hợp? Bài báo [3] đã chứng minh với mỗi tập Separator Ranks khác nhau, traffic
có thể được tính mà khơng quan tâm đến băng thông và thời gian truyền tải nội

dung qua công thức:

𝑇𝑒𝑠𝑡 = ∑ ∑ ∑ 𝑒𝑖𝑗 𝑝𝑖𝑘 𝑦𝑖𝑗𝑘
𝐼

𝐽

𝐾

Với 𝑇𝑒𝑠𝑡 là tổng traffic trong mạng, 𝑒𝑖𝑗 là số đường mà nội dung k đi đến
với người dùng thứ i từ Edge Server, 𝑝𝑖𝑘 là xác suất yêu cầu mà người dùng i đối
với nội dung k, 𝑦𝑖𝑗𝑘 là một biến nhị phân cho biết Cache Server j lưu trữ nội dung
k là máy chủ gần nhất với người dùng i. I, J, K tương ứng với số người dùng, số
Edge Server và số nội dung được lưu trữ ở Origin Server [3].
Bài báo [6] cũng đưa một số ràng buộc để tìm ra Separator Ranks tối ưu để
giảm tối thiểu traffic trong trường hợp 4 màu là
9


𝑎 ≤𝑏 ≤𝑐 ≤𝑑

(1)

𝑎+𝑏+𝑐+𝑑 =4∗𝐶

(2)

Với a, b, c, d là các Separator Ranks của các lớp phổ biến ứng với 4, 3, 2,
1 màu. Ràng buộc (1) chỉ ra rằng, Separator Ranks của lớp phổ biến hơn sẽ nhỏ
hơn hoặc bằng Separator Ranks của lớp phổ biến ít hơn. Ràng buộc (2) miêu tả

tổng không gian lưu trữ trong mạng không vượt quá tổng không gian lưu trữ của
tất cả các Edge Server, trong đó, C là số lượng nội dung mà Edge Server có thể
lưu trữ. Từ kết luận trên, với bài tốn tơ N màu, Separator Ranks có thể được lưu
trong một mảng N phần tử và đáp ứng các ràng buộc sau:

𝑆[0] ≤ 𝑆[1] ≤ . . . ≤ 𝑆[𝑁 − 1]
𝑆[0] + 𝑆[1] + . . . + 𝑆[𝑁 − 1] = 𝑁 ∗ 𝐶

{

2.1.3. Giải thuật định tuyến dựa theo màu (Color-based Routing)
Bên cạnh việc lưu trữ bản sao của nội dung trên các Edge Server, định
tuyến trong mạng CDNs cũng rất quan trọng trong việc chi phối mạng toàn bộ
traffic. Khi nhận một yêu cầu cho một nội dung mà Edge Server đó khơng lưu
trữ, thơng thường Edge Server sẽ gửi u cầu đó về Origin Server để lấy nội dung
đó. Lúc này thuật tốn Dijkstra [9] được sử dụng để tìm đường đi ngắn nhất từ
Edge Server về Origin Server. Tuy nhiên, đường đi ngắn nhất này đơi khi có thể
đi qua các Edge Server khác, nơi có thể chứa những nội dung đang được yêu cầu.
Điều này cho thấy rằng, các thuật tốn định tuyến thơng thường khơng khai thác
được thế mạnh của chiến lược Cooperative caching. Hơn nữa, nếu có quá nhiều
yêu cầu gửi về Origin Server có thể gây ra tắt nghẽn, làm giảm hiệu suất của mạng
CDNs.
Nakajima và các cộng sự [4] đã đề suất được lược đồ định tuyến dựa theo
màu để tận dụng lợi thế của các thẻ màu nhàm giảm tải traffic và chi phí định
tuyến bằng cách bổ sung thêm hai bẳng định tuyến khác. Bảng định tuyến thứ
nhất là Bảng định tuyến yêu cầu (Request Routing Table) nhằm lưu trữ thông tin
về màu sắc và ID tương ứng. Bảng định tuyến thứ hai là Bảng định tuyến đáp ứng
10



(Response Routing Table) nhằm lưu trữ địa chỉ mạng và giao diện phản hồi khi
tìm thấy nội dung được yêu cầu. Chính vì giải thuật tơ màu các Edge Server dựa
trên thuật tốn Welsh-Powell cải tiến, nên chúng ta có thể gom nhóm các Cache
Server gần nhau nhưng khác màu thành các cụm nhỏ. Cụ thể hơn, các thẻ màu
của nội dung được thể hiện trong các yêu cầu gửi đến các Edge Server. Khi này
Edge Server sẽ kiểm tra không gian lưu trữ LFU và LRU. Nếu nội dung đó được
tìm thấy, Edge Server sẽ trả lời trực tiếp cho yêu cầu đó và ngược lại, yêu cầu đó
sẽ chuyển tiếp đến Cache Server cùng màu gần nhất thông qua Bảng định tuyến
yêu cầu. Nếu là một nội dung mới, không màu, yêu cầu sẽ được chuyển tiếp như
mặc định.
Các kết quả thử nghiệm trong bài báo [6] cũng đã cho thấy được giải thuật
định tuyến dựa theo màu làm giảm 30% lưu lượng đường truyền so với giải thuật
định tuyến đường đi ngắn nhất (Shortest-path routing). Giải thuật định tuyến
đường đi ngắn nhất đã giảm tải số lượng yêu cầu tới Origin Server nhưng lưu
lượng đường truyền có thể tối ưu hơn bằng cách sử dụng các thẻ màu. Hình 3 mơ
tả khái niệm cơ bản của giải thuật định tuyến dựa theo màu so với giải thuật định
tuyến đường đi ngắn nhất. Nội dung người dùng yêu cầu được đánh tag 0011.
Như vậy những Edge Server được đánh màu 0001 và 0010 sẽ chứa nội dung đó.
Yêu cầu ban đầu đi vào Edge Server có thẻ màu 1000. Edge Server này không
chứa nội dung được yêu cầu và theo giải thuật định tuyến đường đi ngắn nhất,
yêu cầu sẽ được chuyển tiếp cho Edge Server 0100 và về Orgin Server. Tuy nhiên
với giải thuật định tuyến dựa theo màu, bảng định tuyến sẽ điều hướng yêu cầu
sang Edge Server có thẻ màu 0001 gần nhất và trả về nội dung cho người dùng
yêu cầu.

11


Hình 3. Mơ phỏng giải thuật Color-based Routing và Shortest-path routing [4]


2.2. Phương pháp lấy mẫu
Lấy mẫu là phương pháp lựa chọn một số phần tử để tạo thành một tập hợp
có thể quan sát được từ một quần thể nhằm ước tính hoặc đánh giá tồn bộ quần
thể đó. Lấy ví dụ như, khi có một cuộc điều tra ý kiến quốc gia, chỉ có một mẫu
người dân được tiếp xúc và lấy ý kiến. Ý kiến của mẫu người dân này sẽ đại diện
cho toàn bộ người trong quốc gia đó [10].
Áp dụng các phương pháp chọn mẫu để tìm ra mẫu đặc trưng là một việc
đơn giản, nhưng để xác định mẫu mà chúng ta đạt được có thật sự tốt hay khơng
lại là một vấn đề khác. Một mẫu tốt là mẫu có đầy đủ tất cả các điểm đặc trưng
của quần thể. Mỗi cá thể trong quần thể đều phải có cơ hội được chọn ngẫu nhiên
như nhau. Ngồi ra, mẫu được chọn phải có tính hợp lệ, tính đúng đắn và tính
chính xác. Các tính chất này có thể được chứng minh về mặt tốn học hay bằng
cách làm thí nghiệm để kiểm chứng. Ví dụ như một quần thể có 100 người trong
đó có 50 người mặc áo đỏ, 30 người mặc áo xanh và 20 người mặc áo vàng. Như
vậy, mẫu mà chúng ta trích xuất từ quần thể cũng phải có tỉ lệ tương ứng 50% đỏ,
30% xanh và 20% vàng.
Để tìm ra được một mẫu đặc trưng tốt, trước tiên ta cũng phải thiết lập các
bước thiết kế mẫu. Dựa vào bài toán mà ta quan tâm, ta phải đưa ra được mục
tiêu nghiên cứu, các đặc tính mà chúng ta quan tâm trong một quần thể. Ví dụ
12


như ta đang quan tâm mối quan hệ giữa cân nặng và chiều cao trong một quần
thể thì ngồi những đặc tính như cân nặng, chiều cao của mỗi người thì độ tuổi
cũng là một đặc tính cần xem xét. Ngoài ra, một số tham số mà ta cần quan tâm
như phương sai, giá trị trung bình, kích cỡ của mẫu,… Mẫu lấy bao nhiêu phần
tử của quần thể là phù hợp? Đây cũng là câu hỏi mà các nhà khoa học dữ liệu
phải đặt ra. Nếu lấy quá ít thì khơng đủ dữ liệu để khai thác giá trị hoặc dẫn đến
giá trị không phù hợp. Ngược lại, nếu lấy q nhiều thì việc lấy mẫu khơng có
nhiều ý nghĩa. Vì vậy, việc lấy mẫu cũng phải tuân theo một số quy tắc nhất định

như:
●

Đặc tính trong quần thể biến thiên càng nhiều thì kích cỡ của mẫu

phải lớn để đạt tính chính xác.
●

Mẫu càng lớn thì phạm vi sai số càng nhỏ.

●

Mẫu càng lớn thì mức độ tin cậy càng cao

Có hai kĩ thuật lấy mẫu chính mà ta thường gặp là lấy mẫu ngẫu nhiên và
lấy mẫu phi ngẫu nhiên. Tuỳ vào bài toán mà chúng ta có thể lựa chọn những kỹ
thuật lấy mẫu phù hợp.
Phương pháp lấy mẫu ngẫu nhiên
+ Simple Random Sampling: Đây là kĩ thuật lấy mẫu một cách ngẫu nhiên
bằng cách chọn ra n phần tử trong N sao cho mọi mẫu riêng biệt trong C_N^n có
cơ hội được lựa chọn như nhau, với n là kích thước của mẫu và N là kích thước
của quần thể. Đầu tiên, chúng ta sẽ đánh số các phần tử từ 1 đến N. Sau đó, chúng
ta có thể sử dụng Random Number Tables hay các phần mềm Random Number
Generator để lấy mẫu. Hình bên dưới là ví dụ của Random Number Table.

13


Hình 4. Ví dụ về Random Number Table


Ưu điểm của hướng tiếp cận này là chúng ta không quan tâm đến kích cỡ
của quần thể và rất dễ để áp dụng. Ngược lại, nhược điểm của phương pháp này
là tốn nhiều thời gian và có sai số lớn. Phương pháp này thích hợp với các bài
tốn khơng có nhiều thơng tin về tập mẫu.
+ Stratified Sampling: Phương pháp này chia quần thể thành các nhóm nhỏ
dựa trên tính tương đồng (Similarity) sau đó chọn ngẫu nhiên các cá thể trong
từng nhóm. Phương pháp này phù hợp với các bài tốn có nhiều thơng tin về quần
thể. Tuy nhiên, cần lưu ý rằng, việc chia nhóm càng nhiều thì chi phí cho phương
pháp này càng lớn. Bên cạnh đó, việc chia các nhóm nhỏ cũng cần được cân nhắc,
ví dụ như nếu tổng là 200 thì nên chia 4 nhóm hay 10 nhóm là hợp lý. Hướng tiếp
cận này có ưu điểm làm đảm bảo mức đại diện cho từng nhóm nghiên cứu, kiểm
sốt kích thước mẫu ở các nhóm nhỏ, tăng hiệu quả cho việc thống kê và có thể
áp dụng nhiều phương pháp lấy mẫu khác nhau cho từng nhóm. Nhược điểm thì
như đề cập ở trên, việc chia nhóm sẽ gây tốn kém chi phí cũng như việc lựa chọn
ở các nhóm có tỉ lệ khác nhau.
+ Cluster Sampling: Tương tự như Stratified Sampling, chúng ta cũng chia
quần thể thành từng nhóm nhỏ. Nhưng với phương pháp này, các nhóm nhỏ
khơng dựa trên tính tương đồng mà dựa trên tính đa dạng của quần thể. Các đặc
điểm tiềm năng của quần thể đều được thể hiện trong mỗi cụm nhỏ. Sau đó, ta sẽ

14


chọn các cụm một cách ngẫu nhiên và tổng hợp thành tập mẫu. Một số chiến lược
để chọn cụm:
+ Single Stage Cluster Sampling - các cụm sẽ được chọn ngẫu nhiên và
tổng hợp thành mẫu
+ Two Stage Cluster Sampling - sau khi lựa chọn ngẫu nhiên các cụm, các
phần tử trong mỗi cụm sẽ được lựa chọn ngẫu nhiên lần nữa
+ Multi-Stage Sampling: Kết hợp một hay nhiều phương pháp trên để lấy

mẫu. Tương tự với Two Stage Cluster Sampling, quần thể sẽ được chia thành
từng nhóm nhỏ và áp dụng các kỹ thuật lấy mẫu lên từng nhóm. Quá trình này sẽ
lặp lại nhiều lần đến khi nào cụm không thể phân chia được nữa.
Phương pháp lấy mẫu phi ngẫu nhiên
+ Covenience Sampling: Kỹ thuật này chọn các cá thể trong quần thể bằng
cách dụa trên phần tử dễ lấy nhất. Ví dụ, một tổ chức muốn thành lập chi nhánh
tại 10 thành phố trong nước. Họ sẽ chọn những thành phố nào gần với nơi mà
nhân viên của họ sinh sống nhất để tiện việc đi lại. Việc thành lập mẫu với phương
pháp này rất thuận tiện và nhanh chóng. Tuy nhiên, nếu lựa chọn các phần tử dễ
lấy nhất thì mẫu của chúng ta khơng tính tổng quát, một số đặc trưng của quần
thể sẽ bị mất đi. Phương pháp này không phù hợp với những dữ liệu đa dạng về
đặc tính.
+ Purposive Sampling / Judemental Sampling: Phương pháp này sử dụng
cho mục đích nghiên cứu, chọn ra các cá thể trong quần thể để đạt được mục tiêu
một cách tốt nhất. Phương pháp này chỉ áp dụng với các mẫu nhỏ có chứa các
phần tử đặc biệt chứa nhiều thông tin hoặc ở giai đoạn đầu của việc nghiên cứu.
+ Quota Sampling: Kỹ thuật này lấy mẫu dựa trên một số tiêu chuẩn thiết
lập từ trước, tỷ lệ nhóm cá thể trong tập mẫu phải giống nhau. Các cá thể được
chọn cho đến khi chúng đạt đúng tỉ lẹ của một loại dữ liệu. Ví dụ đơn giản, nếu
chúng ta biết rằng trái đất có 6 tỷ người, trong đó có 55% nam và 45% nữ thì
trong một tập mẫu 1000 người thì 45% trong đó là nữ và 55% là nam. Phương
15


pháp này có ưu điểm là đảm bảo mức độ đại diện của tập mẫu, tuy nhiên mức độ
tổng quán cho quần thể lại thấp và phụ thuộc rất nhiều vào dữ liệu ban đầu.
+ Referral / Snowball Sampling: Chọn mẫu mở rộng dần từ những phần tử
ban đầu. Trước hết, ta tìm ra cá thể đầu tiên trong quần thể rồi nhờ cá thể đó gợi
ý cho các cá thể tiếp theo với điều kiện thoả nhu cầu lấy mẫu nghiên cứu. Điều
này sẽ làm cho tập mẫu tăng dần theo cấp số nhân. Ví dụ đơn giản cho phương

pháp này, với ngữ cảnh là khảo sát về những người bị nhiểm HIV, những người
này có khuynh hướng khơng cởi mở và khó để chúng ta tiếp cận. Để giải quyết,
chúng ta có thể liên hệ với một người liên quan, nhờ họ làm cầu nối giữa ta và
những người bị nhiễm và thu thập thông tin từ họ.
Hồ chứa mẫu ( Reservoir Sampling)
Trong lĩnh vực Big Data, dữ liệu được sinh ra liên tục. Vì thế chúng ta cần
một thuật toán lấy mẫu phù hợp với dạng dữ liệu streaming. Theo Mohammed
AI-Kateb [11], Reservoir Sampling là một kỹ thuật lấy mẫu ngẫu nhiên phù hợp
với dạng dữ liệu liên tục. Kỹ thuật lấy mẫu này cũng phù hợp cho các cụm tính
tốn bị giới hạn về khả năng xử lý. Lý do là vì Reservoir Sampling cho phép giới
hạn về kích thước của mẫu và khơng cần phải duyệt qua tồn bộ tập dữ liệu. Do
đó, kỹ thuật lấy mẫu này khơng quan tâm đến kích thước của quần thể.
Ban đầu, cần phải xác định được kích thước của hồ chứa mẫu. Kích thước
của hồ là cố định và đại diện bằng tham số r. Sau đó, thuật toán sẽ duyệt qua các
phần tử trong tập dữ liệu ban đầu. Nếu phần tự được duyệt chưa vượt quá thứ tự
r thì lưu phần tử đó vào hồ chứa mẫu. Nếu phần tử được duyệt đã vượt quá kích
thước của hồ chưa mẫu r thì với xác suất là

𝒓
𝒌

phần tử đó sẽ được thay thế ngẫu

nhiên bằng một phần tử trong hồ chứa mẫu. Sau khi duyệt hết tất cả các phần tử,
hồ chưa mẫu với kích thước r là tập dữ liệu được lấy ngẫu nhiên từ dữ liệu ban
đầu. Hình 5 biểu diễn chi tiết thuật tốn.

16