So sánh lưu trữ với chính sách thay thế nội dung trong mạng hướng nội dung

Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ IX “Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR'9)”; Cần Thơ, ngày 4-5/8/2016 
DOI: 10.15625/vap.2016.00081 
SO SÁNH LƯU TRỮ VỚI CHÍNH SÁCH THAY THẾ 
NỘI DUNG TRONG MẠ G ƯỚNG NỘI DUNG 
Lê Phong Dũ1,2, Lê Tuấn Anh3, Nguyễn Đức Thái4 
1 Trường Đại học Lạc Hồng 
2
 Trường Đại học Trà Vinh 
3
 Trường Đại học Thủ Dầu Một 
4
 Trường Đại học Bách Khoa, Đại học Quốc gia TP.HCM 
TÓM TẮT — CCN (Content Centric Networking) c u ng nh ng n gần c e ộ giải h ch ng 
in e ne ng ơng lai. Trong CCN, d iệu c chu n h nh h – - h ng h nh u n d iệu d ên tên nội 
dung. L u d liệu trong m ng ặc i m của CCN, tức là d liệu c u t i các node trong m ng. Trong nghiên cứu này 
ch ng i sẽ phân tích các ch nh ch u nội dung t i các node và tiến hành so sánh các ch nh ch n với các chính sách thay 
thế nội dung, khi kh ng gi n u t i c c n de kh ng ủ bộ nhớ u nội dung mới ồng thời mô phỏng c th c hiện trong 
mô h nh m ng t do h h ới ng CCN thay vì mô hình m ng phân c p. Kế uả hỏng ch h ch nh ch h hế nội 
dung LR ch kế uả ố hơn c c ch nh ch c u kh c. 
 —Content Centric Networking, CCN, Cache. 
I. GIỚI THIỆU 
Internet đã phát triển nhanh các dịch vụ, dữ liệu trao đổi ngày càng lớn, xu hướng này tiếp tục tăng theo thời 
gian. Theo thống kê của Cisco VNI [1] số lượng IP toàn cầu tăng gấp tám lần trong năm năm qua, tốc độ tăng trung 
bình là là 29% từ năm 2011-2016. Nhu cầu người dùng sử dụng ngày càng nhiều dịch vụ và truy cập lượng dữ liệu 
ngày càng lớn, đặt ra nhiều thách thức cho việc đáp ứng yêu cầu truyền dữ liệu trên mạng như: băng thông lớn, tốc độ 
bit cao, có độ trễ thấp, bảo mật cao. 
Xu hướng kết nối hiện nay có sự thay đổi từ mô hình kiến trúc client-server truyền thống hướng đến tiếp nhận 
và phổ biến nội dung ở nhiều nơi, nghĩa là mô hình kết nối Internet tập trung vào nội dung dữ liệu, không quan tâm 
nhiều đến vị trí vật lý mà nội dung được lưu trữ. Có nhiều nghiên cứu tập trung vào mô hình kết nối dựa vào nội dung 
đã được đề xuất, trong đó có Content Centric Networking được đề xuất bởi PARC (Palo Alto Research Center) được 
xem như là mạng Internet của tương lai. 
Trong CCN, nội dung dữ liệu được ph n thành các chunk [2], m i chunk được xác định bởi tên duy nhất để 
nhận và chuyển tiếp gói tin được sử dụng thay cho địa ch IP. Có hai gói tin trong CCN, interest packet là gói tin yêu 
cầu dữ liệu từ ph a người d ng và data packer mang nội dung được y u cầu Nguồn giữ data packet m i khi nhận được 
các Interest packet có c ng t n y u cầu thì tự động gửi data packet cho người d ng theo cơ chế lưu vết đường đi của 
Interest packet trong các CCN node. 
Trong mạng CCN, m i node gồm ba cấu tr c dữ liệu ch nh [2]: Content tore (C ) là bộ nhớ lưu trữ nội dung 
dữ liệu, Forwarding Information Base (FIB) chứa một danh sách định tuyến dữ liệu và Pending Interest Table (PIT) lưu 
vết các gói tin đang chờ được phục vụ, nghĩa là đã được gửi yêu cầu qua mạng và chờ phản hồi từ mạng. 
Hình 1. Cơ chế định tuyến-chuyển tiếp gói tin tại CCN Router [2] 
Có nhiều ch nh sách đã được đề xuất lưu trữ nội dung tại các node trong mạng CCN như Leave Copy 
Everywhere (LCE) [3][9], Leave Copy Down (LCD) [4][9], Move Copy Down (MCD) [4][9] hay Prob Cache (Prob) 
[6][9]. Bên cạnh đó, bộ nhớ lưu trữ tại các node có không gian bộ nhớ khác nhau, giới hạn về dung lượng, cần có các 
652 NH CH NH CH TRỮ VỚI CHÍNH SÁCH THAY THẾ NỘI DUNG TRONG MẠNG H ỚNG NỘI DUNG 
chính sách loại bỏ các nội dung không còn phù hợp, không còn được sử dụng để được thay thế bởi nội dung mới. Một 
số ch nh sách được sử dụng để thay thế nội d ng như east Rencently sed ( R ) [5], Least Frequently Used (LFU) 
[7], Random (Rand) [8] hay First In First Out (FIFO). 
Trong bài báo này, ch ng tôi ph n t ch và so sánh các ch nh sách lưu trữ nội dung tại các node như LCE, LCD 
và Prob Cache với ba chính sách thay thế nội dung tại node là LRU, RAND và FIFO trong môi trường mạng tự do 
Abilien. Cấu trúc bài báo gồm phần II, trình bày chính sách lưu trữ nội dung tại các node, phần III trình bày chính sách 
thay thế nội dung, phần IV mô phỏng các ch nh sách và đánh giá, phần kết luận trình bày trong phần V. 
II. L D 
Chính sách lưu trữ tại các node có nhiệm vụ lưu trữ nội dung thường xuyên hoặc gần đ y, những nội dung tại 
node sẽ được tham chiếu bởi các node khác trong thời gian sớm nhất ưu trữ nội dung dữ liệu tại các node giúp giảm 
sử dụng băng thông, hạn chế truy cập dữ liệu tại server gốc, hạn chế tắc nghẽn mạng. 
Các ch nh sách được thiết kế tốt để lưu nội dung tại các node trong mạng CCN gi p tiết kiệm bộ nhớ, tránh lãng 
ph băng thông trong mạng. LCE là ch nh sách được định nghĩa mặc định cho mạng CCN Khi người dùng gửi yêu cầu 
về dữ liệu đến mạng CCN, khi yêu cầu nội dung dữ liệu được tìm thấy tại một node thứ i hoặc server gốc thì nội dung 
yêu cầu được lưu bản sao nội dung dữ liệu tại tất cả các node trung gian từ node thứ (i-1,i-2,,1) tr n đường từ vị trí 
nội dung được tìm thấy đến vị tr người dùng yêu cầu. Kết quả là nội dung dữ liệu được lưu trữ phổ biến trong mạng, 
gần với yêu cầu người dùng. Tuy nhiên, nó tốn nhiều không gian lưu trữ và dữ liệu bị trùng lặp, các node sẽ nhanh 
chóng hết không gian lưu trữ và các chính sách thay thế sẽ phải thực hiện liên tục tại các node. Các chính sách thay thế 
nội dung dữ liệu thường được sử dụng trong LCE này là LRU, FIFO, RAND. 
Trong khi LCD lưu trữ bản sao nội dung dữ liệu tại node mức i-1, khi yêu cầu nội dung được tìm thấy tại một 
node thứ i, thì nội dung dữ liệu ch được lưu trữ tại node ph a dưới node tìm thấy nội dung tại node thứ i. Đối với LCD, 
nó đã giải quyết được vấn đề trùng lặp dữ liệu cũng như tiết kiệm không gian bộ nhớ nhưng nội dung yêu cầu dữ liệu 
tại các node suy giảm. Một dạng khác của LCD là MCD cũng được đề xuất, trong ch nh sách này, khi lưu bản sao nội 
dung dữ liệu tại node thứ i-1 thì nội dung dữ liệu tại node thứ i, nơi y u cầu được tìm thấy dữ liệu sẽ bị xóa. 
Một đề xuất khác là ch nh sách dựa vào xác suất là Prob cache, m i node sẽ lưu trữ một bản sao nội dung dữ 
liệu với xác suất p và không lưu với xác suất 1-p. Khi xác suất là 1, thực hiện ch nh sách LCE. Ch nh sách này đã giải 
quyết được các vấn đề khó khăn của LCE và LCD gặp phải. Mô tả các ch nh sách lưu trữ nội dung tại các node được 
thể hiện trong hình 2. 
Hình 2: Các ch nh sách lưu trữ nội dung 
III. C D 
 i node đều có k ch thước bộ nhớ và khả năng lưu trữ khác nhau, bên cạnh đó, dữ liệu luôn thay đổi thường 
xuyên theo thời gian, các ch nh sách thu hồi bộ nhớ cũng được đề xuất để thu hồi v ng nhớ sao cho hiệu quả tại các 
node Khi một dữ liệu mới đến node nếu không đủ dung lượng để lưu bản sao nội dung dữ liệu, node phải thực hiện các 
chính sách thu hồi bộ nhớ bằng cách loại bỏ các nội dung dữ liệu dựa vào yếu tố như: thời gian truy cập, số lần truy cập 
hay thứ tự truy cập. 
LRU là ch nh sách thay thế nội dung dữ liệu lưu trữ tại node được sử dụng rộng, nó sử dụng hàng đợi sắp xếp 
nội dung dữ liệu theo trình tự thời gian lần truy cập trước đó Khi không gian bộ nhớ node đầy, sẽ xóa nội dung dữ liệu 
sau c ng và th m nội dung dữ liệu mới vào đầu hàng đợi. 
Trong khi đó, F sắp xếp hàng đợi theo số lượng truy xuất, nội dung dữ liệu t được y u cầu nhất sẽ bị thay 
thế bởi nội dung dữ liệu mới Tuy nhi n, đối với F , nhiều nội dung đã phổ biến trong thời gian dài có thể sẽ giữ lại 
mãi trong bộ nhớ Để tránh trường hợp này, F A đã được đề xuất bằng việc sử dụng một ngư ng đo, nếu giá trị trung 
bình của tất cả số lần truy cập lớn hơn giá trị ngư ng thì số lần truy cập các nội dung dữ liệu bị giảm đi một nữa 
 Phong Dũ, Tuấn Anh, Nguyễn Đức Thái 653 
Chính sách thay thế ngẫu nhiên RAND loại bỏ ngẫu nhiên nội dung dữ liệu được lưu trữ tại node, khi cần lưu nội 
dung dữ liệu mới vào node khi bộ nhớ node đầy. Chính sách thay thế này là thách thức rất lớn khi nội dung quan trọng, phổ 
biến được sử dụng thường xuyên bị thay bởi nội dung ít phổ biến hơn Ngoài ra còn có các ch nh sách thay thế khác như 
FIFO, ch nh sách loại bỏ các nội dung dữ liệu lưu trữ tại bộ nhớ node bằng cách lưu trữ trước loại bỏ trước. 
IV. SO SÁNH L VÀ THAY TH N I DUNG 
Trong phần này, ch ng tôi tiến hành mô phỏng và so sánh các ch nh sách lưu trữ nội dung dữ liệu với các chính 
sách thay thế nội dung, so sánh các kết quả của chúng. So sánh kết quả của từng ch nh sách lưu trữ LCE, LCD và Prob 
với ba chính sách thay thế là LRU, RAND và FIFO. Ch ng tôi sử dụng nội dung dữ liệu được tìm thấy tại m i node 
(hit chunk) để làm tham số để so sánh Các ch nh sách được mô phỏng trong mô hình mạng Abilene như hình 3, mà 
kiến tr c mạng này phù hợp với kiến trúc mạng CCN, sử dụng công cụ mô phỏng ccnSim [10] cùng bộ tham số mô 
phỏng được trình bày trong bảng 1. 
Bảng 1. Thông số mô phỏng 
Thông số Giá trị 
Thời gian thực hiện 1800 giây 
Số chunk 10000 
Tốc độ 1 yêu cầu/ giây 
window 60 
Ch nh sách lưu trữ nội dung LCE, LCD, Prob 
Chính sách thay thế nội dung LRU, RAND, FIFO 
Kiến trúc mạng Abilene 
 nh . ô hình mạng Abilene 
A. Ch nh sách lưu trữ LCE 
 CE được sử dụng phổ biến để lưu trữ nội dung trong mạng CCN Thử thách lớn nhất của nó là tr ng lập nội 
dung giữa các node Tuy nhi n trong mạng y u cầu phổ biến nội dung như CCN thì CE vẫn là tốt nhất Trong chính 
sách thay thế nội dung, thì nó có thể được thay thế hết tất cả nội dung dữ liệu trong tất cả các node của nó. Kết quả mô 
phỏng như hình 4 cho thấy, ch nh sách thay thế nội dung R cho kết quả cao hơn trong LCE so với phương pháp 
thay thế RAND và FIF . 
 nh . Ch nh sách lưu trữ LCE và chính sách thay thế nội dung LRU, RAND, FIFO 
654 NH CH NH CH TRỮ VỚI CHÍNH SÁCH THAY THẾ NỘI DUNG TRONG MẠNG H ỚNG NỘI DUNG 
B. Ch nh sách lưu trữ LCD 
Đối với LCD ch lưu trữ nội dung tại các node láng giềng sau khi thấy nội dung cần tìm tại node. Chính sách 
thay thế nội dung được thực hiện khi cần như R , RAND hay FIF , kết quả mô phỏng đối với CD thấy rằng khi sử 
dụng LRU vẫn thực hiện tốt hơn so với hai ch nh sách thay thế còn lại, nó thực hiện công bằng qua các node, không có 
biến thi n lớn nội dung lưu trữ tại các node, kết quả mô phỏng ở hình 5. 
H nh . Ch nh sách lưu trữ LCD và chính sách thay thế nội dung LRU, RAND, FIFO 
C. Ch nh sách lưu trữ Prob 
Đối với ch nh sách Prob lưu trữ nội dung tại các node bằng cách tính xác suất p, trong đó đã giải quyết được 
những thách thức mà trong LCE và LCD gặp phải. Khi thực hiện mô phỏng trong mô hình mạng Abilene chính sách 
thay thế nội dung LRU thực hiện hiệu quả, đạt t lệ tìm thấy nội dung tại các node lớn hơn so với với chính sách còn 
lại. Hình 6 ch ra kết quả so sánh của ch ng tôi. 
 nh 6. Ch nh sách lưu trữ Prob và chính sách thay thế nội dung LRU, RAND, FIFO 
Từ kết quả mô phỏng cho thấy, mặc dù sử dụng nhiều ch nh sách lưu trữ dữ liệu khác nhau thì chính sách thay 
thế nội dung LRU cho kết quả tốt hơn các ch nh sách khác, đánh giá cao hơn về tính hiệu quả của ch nh sách LRU khi 
được sử dụng. 
V. K L 
Bài báo đã trình bày các chính sách lưu trữ nội dung dữ liệu cũng như chính sách thay thế nội dung dữ liệu tại 
node trong mạng CCN. Ch ra điểm mạnh, yếu của từng ch nh sách, qua đó tiến hành mô phỏng từng ch nh sách lưu trữ 
nội dụng với các chính sách thay thế nội dung đã đề cập và đánh giá lại LRU được xem là chính sách thay thế nội dung 
hiệu quả hơn các chính sách khác trong CCN. 
 L Ệ 
[1] Cisco visual networking index: forecast and methodology: 2011-2015, 5/2012. 
[2] V. Jacobson, D. K. Smelters, 1. D. Thornton, M. F. Plass, N. H. Briggs, R. L. Braynard, “Networking named content”, ACM 
CoNEXT, Rome, Italy, December 2009. 
[3] G. Carofiglio, V. Gehlen, and D. Perino, “Experimental evaluation of memory management in content-centric 
networking”, IEEE ICC, 2011, pp. 1-6. 
[4] K. Cho, M. Lee, K. Park, T. T. Kwon, Y. Choi, and S. Pack, “Wave: Popularity-based and collaborative in-network 
caching for content-oriented networks”, IEEE INFOCOM WKSHPS, 2012, pp. 316-321. 
 Phong Dũ, Tuấn Anh, Nguyễn Đức Thái 655 
[5] D. He, W. K. Chai, and G. Pavlou. “Leveraging in-network caching for efficient content delivery in content-centric network”, 
Proc. of London Communication Symposium 2011. 
[6] Psaras, Ioannis, Wei Koong Chai, and George Pavlou. “Probabilistic in-network caching for information-centric networks”, 
Proceedings of thesecond edition of the ICN workshop on Information-centric networking. ACM, 2012. 
[7] S. Podlipnig and L. B¨ osz¨ ormenyi, “A survey of web cache replacement strategies,” AC Comput, vol 35, no 4, pp 374–
398, 2003. 
[8] N. Laoutaris, S yntila, and I tavrakakis, “Meta Algorithms for Hierarchical Web Caches”, IEEE ICPCC, 2004. 
[9] N Laoutaris, H Che, and I Stavrakakis, “The LCD interconnection of LRU caches and its analysis”, Performance Evaluation, 
63(7), 2006. 
[10] ccnSim homepage.  05/2016.