Tổng quan nghiên cứu

Internet hiện nay đã trở thành công cụ thiết yếu trong đời sống, với khoảng 5,39 tỷ người dùng toàn cầu, chiếm 67,9% dân số thế giới tính đến cuối năm 2021. Sự phát triển nhanh chóng của số lượng nội dung trên mạng Internet, với hơn 160 triệu website hoạt động, đặt ra thách thức lớn trong việc truyền tải nội dung đến người dùng một cách hiệu quả và nhanh chóng. Mạng phân phối nội dung (Content Delivery Networks - CDN) được xem là giải pháp quan trọng nhằm giảm thiểu độ trễ và tăng trải nghiệm người dùng bằng cách phân phối nội dung từ các Edge Server gần người dùng hơn thay vì từ máy chủ gốc (Origin Server) ở xa.

Tuy nhiên, với sự gia tăng nhanh chóng về số lượng yêu cầu và nội dung, giải thuật tô màu (coloring algorithm) trong mạng CDN, vốn được sử dụng để tối ưu lưu trữ và định tuyến nội dung, đang gặp phải vấn đề về độ phức tạp tính toán và chi phí truyền tải dữ liệu lớn. Đặc biệt, chi phí truyền tải dữ liệu về trung tâm để tính toán lại giải thuật và thời gian chạy giải thuật tăng cao gây ảnh hưởng đến hiệu suất mạng.

Mục tiêu nghiên cứu của luận văn là cải thiện hiệu suất giải thuật tô màu cho mạng CDN thông qua kỹ thuật lấy mẫu dữ liệu đầu vào, nhằm giảm độ phức tạp và chi phí tính toán. Nghiên cứu tập trung vào hai bài toán lấy mẫu chính: lấy mẫu tập trung và lấy mẫu phân tán, đồng thời đề xuất công thức đánh giá độ tương đồng giữa tập dữ liệu gốc và tập dữ liệu sau khi lấy mẫu. Thực nghiệm được thực hiện trên tập dữ liệu thực tế trích xuất từ một ISP lớn tại Việt Nam, với dữ liệu yêu cầu người dùng trong 24 khoảng thời gian tương ứng mỗi giờ trong ngày 6/12/2018, mô phỏng trên mạng CDN bằng công cụ Mininet.

Kết quả nghiên cứu có ý nghĩa quan trọng trong việc tối ưu hóa mạng CDN, giúp giảm thời gian xử lý giải thuật tô màu, giảm chi phí truyền tải và nâng cao trải nghiệm người dùng thông qua việc cập nhật nhanh chóng các nội dung phổ biến.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên hai lý thuyết chính: mạng phân phối nội dung (CDN) và kỹ thuật lấy mẫu dữ liệu (Data Sampling).

  1. Mạng phân phối nội dung (CDN): CDN là hệ thống các máy chủ phân tán (Edge Server) đặt tại nhiều vị trí địa lý khác nhau, nhằm cung cấp nội dung gần người dùng cuối hơn, giảm độ trễ và tải cho máy chủ gốc. Giải thuật tô màu (coloring algorithm) được áp dụng để gán màu cho các Edge Server và nội dung dựa trên mức độ phổ biến, giúp tối ưu lưu trữ và định tuyến. Chiến lược Hybrid Caching kết hợp Least Frequently Used (LFU) và Least Recently Used (LRU) được sử dụng để quản lý bộ nhớ cache hiệu quả. Giải thuật Welsh-Powell cải tiến được dùng để tô màu các Edge Server với số lượng màu tối thiểu, đồng thời nội dung được đánh màu dựa trên tần suất truy cập.

  2. Kỹ thuật lấy mẫu dữ liệu: Lấy mẫu là phương pháp chọn ra một tập con đại diện cho toàn bộ dữ liệu nhằm giảm khối lượng xử lý mà vẫn giữ được đặc trưng của dữ liệu gốc. Luận văn áp dụng kỹ thuật lấy mẫu ngẫu nhiên, đặc biệt là thuật toán Reservoir Sampling, phù hợp với dữ liệu dạng streaming và có khả năng giới hạn kích thước mẫu cố định. Công thức đánh giá độ tương đồng giữa tập dữ liệu gốc và tập dữ liệu sau lấy mẫu được phát triển dựa trên chỉ số Jaccard, có trọng số alpha biểu thị mức độ quan trọng của từng lớp màu trong giải thuật tô màu.

Các khái niệm chính bao gồm: Edge Server, Origin Server, giải thuật tô màu, Hybrid Caching, Reservoir Sampling, chỉ số Jaccard, Separator Ranks (tập số phân loại mức độ phổ biến nội dung).

Phương pháp nghiên cứu

Nghiên cứu sử dụng dữ liệu thực tế từ một ISP lớn tại Việt Nam, gồm hơn 20 triệu yêu cầu truy cập với 4.032.295 nội dung trong ngày 6/12/2018, chia thành 24 khoảng thời gian mỗi giờ. Mạng CDN được mô phỏng bằng công cụ Mininet với 4 Edge Server, 4 Client và 1 Origin Server. Mỗi Edge Server được cấu hình theo chiến lược Hybrid Caching.

Quá trình nghiên cứu gồm các bước:

  • Tiền xử lý dữ liệu Access Log thành các Data Frame sử dụng Apache Spark để xử lý song song và lấy mẫu.
  • Thực hiện lấy mẫu tập trung sau khi tập hợp toàn bộ dữ liệu từ các Edge Server và lấy mẫu phân tán ngay trên từng Edge Server trước khi gửi về trung tâm.
  • Áp dụng giải thuật tô màu trên dữ liệu gốc và dữ liệu sau lấy mẫu để tính toán tập số Separator Ranks.
  • Đánh giá độ tương đồng giữa kết quả trước và sau lấy mẫu bằng công thức Jaccard có trọng số.
  • So sánh thời gian chạy giải thuật tô màu trên dữ liệu gốc và dữ liệu lấy mẫu để đánh giá hiệu quả cải thiện.

Cỡ mẫu lấy mẫu được điều chỉnh từ 10% đến 70% số lượng yêu cầu ban đầu để đánh giá ảnh hưởng đến thời gian xử lý và độ tương đồng dữ liệu. Phương pháp chọn mẫu Reservoir Sampling được lựa chọn do tính hiệu quả và khả năng xử lý dữ liệu streaming.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

  1. Giảm thời gian chạy giải thuật tô màu: Khi lấy mẫu với kích thước 10% số lượng yêu cầu ban đầu, số lượng nội dung giảm khoảng 83%, dẫn đến thời gian chạy giải thuật nhanh gấp 7 lần so với dữ liệu gốc. Khi kích thước mẫu tăng lên 30%, thời gian chạy nhanh hơn tối đa 3 lần. Điều này chứng tỏ mối quan hệ lũy thừa giữa số lượng nội dung và độ phức tạp giải thuật.

  2. So sánh lấy mẫu tập trung và phân tán: Lấy mẫu phân tán trên các Edge Server cho thời gian chạy giải thuật nhanh hơn lấy mẫu tập trung khoảng 14 giây, đồng thời giảm chi phí truyền tải dữ liệu về trung tâm. Tuy nhiên, sự khác biệt về thời gian không quá lớn.

  3. Độ tương đồng dữ liệu sau lấy mẫu: Độ tương đồng giữa tập số Separator Ranks trước và sau lấy mẫu được đánh giá bằng công thức Jaccard có trọng số, đạt giá trị cao gần 1 trong hầu hết các khoảng thời gian, chỉ có khoảng 8% các khoảng thời gian có độ tương đồng thấp do số lượng yêu cầu và nội dung quá thấp.

  4. Giữ nguyên đặc tính dữ liệu: Số lượng yêu cầu và nội dung sau lấy mẫu vẫn giữ được biến thiên tương tự dữ liệu gốc theo từng khoảng thời gian. Đặc biệt, 20 nội dung phổ biến nhất vẫn được giữ lại với tần suất truy cập tương đồng, đảm bảo tính đại diện của mẫu.

Thảo luận kết quả

Kết quả thực nghiệm khẳng định tính hiệu quả của kỹ thuật lấy mẫu trong việc giảm độ phức tạp và thời gian xử lý giải thuật tô màu cho mạng CDN. Việc giảm số lượng yêu cầu và nội dung đầu vào làm giảm đáng kể chi phí tính toán mà không làm mất đi đặc trưng quan trọng của dữ liệu, như mức độ phổ biến của các nội dung chủ chốt.

So với các nghiên cứu trước đây sử dụng dữ liệu giả lập phân phối Gamma, kết quả thực nghiệm trên dữ liệu thực tế của ISP Việt Nam cho thấy tính khả thi và ứng dụng thực tiễn cao hơn. Việc áp dụng lấy mẫu phân tán còn giúp giảm tải chi phí truyền tải dữ liệu về trung tâm, phù hợp với các mạng CDN quy mô lớn.

Độ tương đồng không tuyệt đối giữa tập số Separator Ranks trước và sau lấy mẫu được giải thích do sự thay đổi thứ tự ID nội dung sau khi lấy mẫu, ảnh hưởng đến việc phân loại màu sắc. Điều này nhấn mạnh cần lưu ý khi đánh giá độ tương đồng và có thể cải tiến thuật toán lấy mẫu để giữ nguyên thứ tự hoặc trọng số nội dung.

Dữ liệu được trình bày qua biểu đồ thời gian chạy giải thuật theo kích thước mẫu, biểu đồ số lượng yêu cầu và nội dung theo thời gian trước và sau lấy mẫu, cũng như bảng kết quả độ tương đồng Separator Ranks, giúp minh họa rõ ràng hiệu quả và tính đại diện của phương pháp.

Đề xuất và khuyến nghị

  1. Áp dụng kỹ thuật lấy mẫu phân tán trên các Edge Server: Động từ hành động: triển khai; Target metric: giảm chi phí truyền tải dữ liệu về trung tâm ít nhất 30%; Timeline: 6 tháng; Chủ thể thực hiện: các nhà quản lý mạng CDN và kỹ sư hệ thống.

  2. Tối ưu kích thước hồ chứa mẫu (Reservoir size): Động từ hành động: điều chỉnh; Target metric: cân bằng giữa thời gian xử lý và độ chính xác dữ liệu (độ tương đồng > 0.9); Timeline: 3 tháng; Chủ thể thực hiện: nhóm nghiên cứu và phát triển thuật toán.

  3. Phát triển thuật toán lấy mẫu có trọng số (Weighted Reservoir Sampling): Động từ hành động: nghiên cứu và triển khai; Target metric: giữ nguyên đặc tính nội dung phổ biến, giảm mất mát dữ liệu quan trọng; Timeline: 12 tháng; Chủ thể thực hiện: nhóm nghiên cứu khoa học máy tính.

  4. Tích hợp dự báo nội dung phổ biến tương lai: Động từ hành động: xây dựng mô hình dự báo; Target metric: tăng tỷ lệ hit cache trên Edge Server lên 10%; Timeline: 18 tháng; Chủ thể thực hiện: nhóm phát triển sản phẩm CDN.

  5. Đào tạo và nâng cao nhận thức cho đội ngũ vận hành: Động từ hành động: tổ chức khóa đào tạo; Target metric: 100% kỹ sư vận hành hiểu và áp dụng kỹ thuật lấy mẫu; Timeline: 3 tháng; Chủ thể thực hiện: phòng nhân sự và đào tạo.

Đối tượng nên tham khảo luận văn

  1. Nhà nghiên cứu và sinh viên ngành Khoa học Máy tính: Luận văn cung cấp kiến thức chuyên sâu về mạng CDN, giải thuật tô màu và kỹ thuật lấy mẫu, hỗ trợ nghiên cứu và phát triển các thuật toán tối ưu mạng.

  2. Kỹ sư phát triển và vận hành mạng CDN: Tham khảo để áp dụng kỹ thuật lấy mẫu giảm tải dữ liệu, cải thiện hiệu suất hệ thống và giảm chi phí vận hành.

  3. Các nhà quản lý hệ thống mạng và dịch vụ Internet: Hiểu rõ về các giải pháp tối ưu mạng CDN, từ đó hoạch định chiến lược đầu tư và nâng cấp hạ tầng phù hợp.

  4. Doanh nghiệp cung cấp dịch vụ nội dung trực tuyến (Video-on-Demand, mạng xã hội): Áp dụng các giải pháp tối ưu phân phối nội dung, nâng cao trải nghiệm người dùng và giảm chi phí băng thông.

Câu hỏi thường gặp

  1. Lấy mẫu dữ liệu đầu vào giúp cải thiện giải thuật tô màu như thế nào?
    Lấy mẫu giúp giảm số lượng yêu cầu và nội dung đầu vào, từ đó giảm độ phức tạp tính toán và thời gian chạy giải thuật tô màu. Ví dụ, lấy mẫu 10% số lượng yêu cầu giúp giảm thời gian chạy nhanh gấp 7 lần so với dữ liệu gốc.

  2. Tại sao cần phân biệt lấy mẫu tập trung và lấy mẫu phân tán?
    Lấy mẫu tập trung thực hiện sau khi tập hợp toàn bộ dữ liệu về trung tâm, gây chi phí truyền tải lớn. Lấy mẫu phân tán thực hiện ngay trên các Edge Server, giảm chi phí truyền tải và cân bằng tải xử lý.

  3. Độ tương đồng dữ liệu sau lấy mẫu được đánh giá như thế nào?
    Sử dụng công thức Jaccard có trọng số alpha để tính độ tương đồng giữa tập số Separator Ranks trước và sau lấy mẫu. Giá trị gần 1 cho thấy dữ liệu sau lấy mẫu giữ được đặc trưng của dữ liệu gốc.

  4. Có những hạn chế nào khi áp dụng kỹ thuật lấy mẫu?
    Một số nội dung có tần suất truy cập thấp có thể bị loại bỏ trong quá trình lấy mẫu, ảnh hưởng đến độ chính xác phân loại màu sắc. Ngoài ra, sự thay đổi thứ tự ID nội dung sau lấy mẫu có thể gây sai lệch trong đánh giá.

  5. Luận văn có đề xuất hướng phát triển nào cho tương lai?
    Có đề xuất nghiên cứu các phương pháp lấy mẫu cải tiến như Weighted Reservoir Sampling để giữ trọng số nội dung, cũng như tích hợp mô hình dự báo nội dung phổ biến nhằm nâng cao hiệu quả lưu trữ và phân phối.

Kết luận

  • Luận văn chứng minh tính cần thiết và hiệu quả của kỹ thuật lấy mẫu trong việc cải thiện giải thuật tô màu cho mạng CDN, giảm đáng kể thời gian xử lý và chi phí truyền tải.
  • Đề xuất công thức đánh giá độ tương đồng dữ liệu trước và sau lấy mẫu dựa trên chỉ số Jaccard có trọng số, giúp đánh giá chính xác mức độ giữ nguyên đặc trưng dữ liệu.
  • Thực nghiệm trên dữ liệu thực tế từ ISP Việt Nam cho thấy lấy mẫu 10% giúp tăng tốc giải thuật gấp 7 lần, đồng thời giữ được đặc tính phổ biến của nội dung.
  • Lấy mẫu phân tán trên các Edge Server là hướng tiếp cận ưu việt, giảm tải chi phí truyền tải và cân bằng xử lý.
  • Hướng phát triển tiếp theo bao gồm nghiên cứu các thuật toán lấy mẫu cải tiến và tích hợp dự báo nội dung phổ biến để tối ưu hóa mạng CDN hơn nữa.

Next steps: Triển khai thử nghiệm kỹ thuật lấy mẫu phân tán trong môi trường mạng CDN thực tế, phát triển thuật toán Weighted Reservoir Sampling và xây dựng mô hình dự báo nội dung phổ biến.

Các nhà nghiên cứu và kỹ sư mạng CDN nên áp dụng và tiếp tục phát triển kỹ thuật lấy mẫu để nâng cao hiệu quả vận hành mạng phân phối nội dung trong bối cảnh dữ liệu ngày càng tăng nhanh.