Đề xuất thuật toán thay thế cache cho kiến trúc internet web caching của nhà cung cấp dịch vụ internet

 chúng tôi lựa 
chọn kiến trúc lai và phân tích đánh giá hiệu năng sử dụng mô hình hàng đợi với các cấp 
cache: Institution Caches (IC), Regional Caches (RC), Central Caches (CC), Origin 
Caches (OC) [11]. 
Thông thường, các IC kết nối ở các nút POP địa phương (Point-Of-Presence), các RC 
kết nối ở các nút khu vực, và các CC kết nối ở mạng trục quốc gia, còn OC ở mạng kết nối 
Điều khiển – Cơ điện tử - Truyền thông 
 N. X. Trường, H. K. Lâm, “Đề xuất thuật toán thay thế cache cung cấp dịch vụ Internet.” 56 
các Origin Web Servers. Các hệ thống Cache Engine có thể cài đặt cho các IC, RC, CC, và 
OC. Như vậy, các hệ thống cache phải thực hiện các thuật toán thay thế Web Cache phân 
tán theo từng tầng và giữa các tầng. 
Thời gian đáp ứng trung bình cho truy nhập HTTP trong một kiến trúc Web caching 
phân tầng của ISP đã được chúng tôi đề xuất trong [11]: 
])))[)((][)((][)((][][ 0112233 HHHHWC REMissREMissREMissRERE (1) 
][],[],[],[ 0123 HHHH RERERERE - Thời gian đáp ứng truy nhập trung bình của các 
cấp cache tương ứng: IC, RC, CC, và OC 
123 ,, MissMissMiss - Tỷ số trượt cache (cache miss) ở các cấp cache tương ứng: IC, 
RC, CC, và OC. 
Chúng tôi đề xuất tiến trình đáp ứng các yêu cầu HTTP của mạng ISP với kiến trúc 
Web caching lai cho ở hình 1. Ở hình này, chỉ nêu tiến trình đáp ứng của IC, bởi tiến trình 
ở các cấp RC, CC, và OC cũng tương tự. Cho rằng IC có n Proxy Caches (từ Proxy Cache 
0 đến Proxy Cache n-1), trong đó Proxy Cache 0 ở gần yêu cầu HTTP nhất và Proxy 
Cache n-1 ở xa yêu cầu HTTP nhất. Ưu tiên của quá trình tìm kiếm đối tượng cho yêu cầu 
HTTP ở IC là tìm ở cấp ngang hàng (từ Proxy Cache 0 đến Proxy Cache n-1). Chỉ khi 
trượt IC thì yêu cầu HTTP mới được chuyển lên RC. Tương tự giữa RC và CC, giữa CC 
và OC. 
Hình 1. Tìm đối tượng (Web page) ở IC cho yêu cầu Client HTTP. 
Đặt tỷ số trúng cache HR (Hit Rate) là H và đáp ứng trung bình của từng Proxy Cache 
là R, thì đối với cấp cache IC có tương ứng các giá trị: 
111100 ,,..,,,, ICnICnICICICIC RHRHRH . Tương tự, đối với RC, CC: 
111100 ,,..,,,, RCmRCmRCRCRCRC RHRHRH , 111100 ,,..,,,, CCkCCkCCCCCCCC RHRHRH . 
Đối với OC, xác suất trúng Web cache luôn bằng 1, nghĩa là HOC =1, do đó, Miss0 bằng 
0, nên ta không xét OC trong các công thức dưới đây. 
Đáp ứng trung bình của từng cấp cache là: 
http requests 
Object in Proxy 
Cache 0 ? 
No 
Send Object 
to Client 
Yes 
No 
Yes 
No No 
Object in Proxy 
Cache 1 ? 
Proxy Cache 0 
is full ? 
No 
Yes 
Cache 
Replacement 
No Object already 
in Proxy Cache 
0 ? 
Send Object to 
Proxy Cache 0 
No 
Object in Proxy 
Cache n -2? 
Cache 
Replacement 
Yes 
Proxy Cache 
n-3 is full ? 
Yes 
Object already 
in Proxy Cache 
n-3 ? 
Send Object to 
Proxy Cache n-3 
No 
No 
Object in Proxy 
Cache n-1 ? 
Cache 
Replacement 
Yes 
Proxy Cache 
n-2 is full ? 
Yes 
Object already 
in Proxy Cache 
n-2 ? 
Send Object to 
Proxy Cache n-2 
No 
No 
Yes 
Yes 
To Proxy cache 
n-3 is full ? 
To 
RC 
Yes 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2017 57
)2(...))))(1()(1()(1(][][ 32211003 ICICICICICICICHIC RHRHRHRRERE
)3(...))))(1()(1()(1(][][ 32211002 RCRCRCRCRCRCRCHRC RHRHRHRRERE
)4(...))))(1()(1()(1(][][ 32211001 CCCCCCCCCCCCCCHCC RHRHRHRRERE
)5(...))))(1()(1()(1(][][ 32211000 OCOCOCOCOCOCCOHOC RHRHRHRRERE 
Kết hợp các công thức (1), (2), (3), (4), và (5), nhận được: 
.)1(;)1(;)1(
1
0
1
1
0
2
1
0
3    
k
i
CCi
m
i
RCi
n
i
ICi HMissHMissHMiss (6) 
Số lượng Web cache (Proxy Cache) càng lớn, tỷ số trúng cache (HR) của từng Web 
cache càng cao thì tỷ số trượt (Missi) ở từng cấp cache càng nhỏ. Điều này phụ thuộc vào 
các yếu tố như kích thước các đối tượng Web, dung lượng của các hệ thống Web Cache, 
thuật toán thay thế cache, cấu trúc của toàn bộ từng cấp cache (IC, RC, CC, và OC) trên 
kiến trúc Internet Web Caching. 
Thuật toán LRU chỉ đạt hiệu quả khi các đối tượng Web có kích thước giống nhau. 
Thực tế phụ thuộc vào chỉ số dân trí từng vùng, sự phát triển của các dịch vụ thông tin di 
động tốc độ, dân số trẻ, thì xét theo Zipf [13]: Các hệ thống Web cache thiết lập ở đó cần 
có sự đầu tư về công suất, dung lượng cho đáp ứng nhu cầu. Vậy nên mặc dù cùng cấp 
mạng nhưng các hệ thống Web cache sẽ khác nhau về dung lượng, công suất vì số lượng 
các Website được ưa chuộng khác nhau, kích thước các đối tượng Web cũng khác nhau. 
Do đó, không áp dụng các thuật toán LRU hay LFU một cách đơn thuần. Ngoài ra, có một 
số trang Web có thể một thời điểm không được người dùng quan tâm, và dễ bị thay thế 
theo LRU hay LFU, nhưng sau đó, chúng lại có thể được sự bùng nổ số người tham chiếu 
đến. Khi đó theo LRU hay LFU những trang web này lại phải tìm kiếm qua mạng trên các 
hệ thống Web cache khác, mà chưa chắc đã tồn tại. 
Hình 2. Tiến trình thực hiện thuật toán LRU-EXT. 
Thuật toán của chúng tôi đề xuất khắc phục nhược điểm này bằng cách đưa vào mỗi hệ 
thống Web cache một web cache cục bộ mở rộng LEWC (Local Extended Web Cache) để 
lưu tạm thời các đối tượng Web bị loại bỏ khi thực hiện LRU hay LFU. Để áp dụng thay 
thế cache thuật toán SIZE liên kết kích thước cho từng đối tượng trong Web Cache, và sẽ 
loại bỏ đối tượng có kích thước lớn nhất và ít được tham chiếu gần đây nhất theo LRU. 
Thuật toán LRU-MIN lại loại bỏ các đối tượng có kích thước nhỏ nhất. Thực tế, sự đa 
Điều khiển – Cơ điện tử - Truyền thông 
 N. X. Trường, H. K. Lâm, “Đề xuất thuật toán thay thế cache cung cấp dịch vụ Internet.” 58 
dạng của các đối tượng Web, đặc biệt là các nội dung của các dịch vụ đa phương tiên, 
không làm cho các thuật toán này đạt được hiệu quả cao. Bởi vì ở một thời điểm một đối 
tượng Web được coi là lớn nhất về kích thước nên bị loại bỏ, xong ở thời điểm khác nó 
không phải là lớn nhất. Hoặc ngược lại, một đối tượng bị coi là nhỏ nhất và bị loại bỏ theo 
LRU-MIN nhưng sau đó, nó lại không phải là nhỏ nhất. Do đó, giải pháp đưa vào LEWC 
có thể khắc phục được lỗi của SIZE và LRU-MIN. 
Chúng tôi gọi thuật toán thay thế Web cache đề xuất là LRU-EXT. Như vậy, khi trượt 
đối tượng trong Web cache đầu tiên, thì phải tìm kiếm trong LEWC xem có đối tượng nào 
trước đó bị thay thế trùng với yêu cầu của http. Nếu có thì đó là trúng Web cache. Chỉ khi 
không có trong LEWC, mới phải chuyển yêu cầu http đến Web cache tiếp thep cùng cấp. 
Hình 2 thể hiện tiến trình thực hiện thuật toán thay thế LRU-EXT cho trường hợp Web 
Cache ở cấp IC: IC0 và IC1. 
Vì áp dụng cả SIZE và MIN nên thuật toán cũng kết hợp kích thước cho từng đối tượng 
Web để thực hiện so sánh tìm kiếm vùng thay thế. Các đối tượng trong Web cache được 
sắp xếp theo thứ tự kích thước từ lớn đến nhỏ và ít được tham chiếu gần đây nhất (theo 
LRU-MIN). Khi thực hiện thay thế, trước hết tìm kiếm vùng ít được tham chiếu có kích 
thước vừa cho thay thế (không nhất thiết là phải vùng cuối nhất), thì đối tượng bị thay thế 
được ghi vào LEWC, và đối tượng Web mới từ Web cache lân cận được chuyển vào vùng 
thay thế. Nếu không tìm thấy ở vùng ít được tham chiếu, thì phải tìm kiếm ngoài vùng này 
từ đầu (theo SIZE), nghĩa là đối tượng thay thế có kích thước lớn. Đối tượng bị thay thế 
cũng sẽ được ghi vào LEWC. Trường hợp không có vùng nào đủ kích thước thì phải chọn 
hai vùng lân cận để thay thế. 
3. MÔ PHỎNG, TÍNH TOÁN 
Time 0 1 2 3 4 5 6 7 8 9 10 
Requested web Object to g c a b d j k a c d 
C
ac
h
e 
O
bj
ec
ts
Cache Cache 
k d d d d d d d k k k d 
j c c c c c c c k k k 
i b b b b b b b b b b b 
h a a a a a a j j a a a 
g g g g g g g g g c c 
Miss (M)/Hit (H) M H H H H M M H H H 
Size compare j=a k=d+c j=a c=g 
Hit Rate (HR) 7/10 
Hình 3. Minh họa thực hiện thuật toán LRU-EXT. 
Extended Cache Buffer: 
store replaced Objects in 
Proxy Cache 0 
Replacement results by 
LRU-SIZE-MIN-REST: 
last access queue of Proxy 
Cache 0 
g 
c 
g 
a 
c 
g 
b 
a 
c 
g 
d 
b 
a 
c 
j 
d 
b 
c 
k 
j 
b 
g 
a 
k 
b 
g 
c 
a 
k 
b 
d 
c 
a 
b 
 g g 
a 
a 
d 
c 
d 
c 
j 
d 
j 
g 
j 
g 
k 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2017 59
Minh họa thực hiện thuật toán LRU-EXT như hình 3 giữa hai hệ thống Proxy Cache 0 
và 1 (hay Web Cache), giả định ở Proxy Cache 0 có 4 đối tượng với so sánh kích thước: d 
> c > b> a, và một vùng free, tương tự ở Proxy Cache 1 có các đối tượng Web: k > j > i > 
h > g. Cho rằng kích thước của j = a, k = d+c, c = g. Như vậy, đạt được tỷ số trúng HR là 
7/10 xét trên 10 lần truy nhập. Nếu sử dụng LRU thì phải loại bỏ các đối tượng a, d, c, 
chúng không thể phục hồi được cho Proxy Cache 0 khi có tham chiếu lại, mà chúng cũng 
không có trong Proxy Cache 1 lân cận. Do đó, với LRU chỉ đạt được HR = 4/10. Để không 
lưu trữ các đối tượng Web bị loại trong LEWC lâu và chiếm không gian nhớ, mỗi lần tham 
chiếu lại LEWC thì đối tượng trong LEWC được xóa. HR của thuật toán đề xuất cần phải 
tính cả những đối tượng Web bị thay thế nhưng lại được ghi vào LEWC và sau đó được 
chuyển trở lại Web cache cho đáp ứng yêu cầu HTTP. 
Tỷ số trúng cache của thuật toán LRU-EXT được tính theo công thức sau: 
 in in
LRU EXT
Numberof hitobjinwebcache Numberof hitobjinLEWCHN C HN LEWC
HR
TN Totalnumberof requested obj
 (7) 
Tỷ số trúng cache của thuật toán LRU tính theo công thức sau: 
in
LRU
HN C Number of hit obj in webcache
HR
TN Totalnumber of requested obj
 (8) 
4. KẾT LUẬN 
Từ công thức (7) và (8) cho thấy rõ ràng LRUEXTLRU HRHR khi cùng có chung 
giá trị HNinC. Ngoài ra, vì lấy trực tiếp từ LEWC các đối tượng Web cho đáp ứng yêu cầu 
HTTP nên trễ đáp ứng nhỏ, và thực hiện thuật toán thay thế nhanh. Các quá trình thay thế 
cache ở các Web Cache diễn ra tương tự ở tất cả các cấp cache. Nhược điểm của LRU-
EXT là cần có thêm bộ nhớ Cache mở rộng để lưu các đối tượng Web bị thay thế. Tuy 
nhiên, với công nghệ nhớ hiện nay thì vấn đề dung lượng nhớ dễ dàng giải quyết. 
Để chứng minh thuật toán LRU-EXT có đạt hiệu năng cao khi có nhiều Web cache ở 
từng cấp cache trong kiến trúc Internet Web Caching của mạng ISP sẽ phải thực hiện mô 
phỏng và thử nghiệm với số lượng lớn các yêu cầu HTTP và thực hiện các tính toán công 
thức (1). Để thực hiện mô phỏng và phân tích hiệu năng chúng tôi dự định sử dụng mô 
hình hàng đợi và mạng Petri thời gian ngẫu nhiên. 
TÀI LIỆU THAM KHẢO 
[1]. Pablo Rodriguez, Christian Spanner, Ernst W.Biersack: “Web Caching Architectures: 
Hierarchical and Distributed Caching”.  (4th 
International WWW Caching Workshop), Institut EUROCOM, france, 1999. 
[2]. Mukesh Dawar, Charanjit Singh, “A Review on Web Caching Techniques”. 
International Journal of Advanced Research in Computer Science and Software 
Engineering. Volume 4, Issue 3, March 2014. ISSN: 2277 128X. 
[3]. Kapil Arora, Dhawaleswar Rao Ch, “Web Cache Page Replacement by Using LRU 
and LFU Algorithms with Hit Ratio: A Case Unification”. Kapil Arora et al, / 
(IJCSIT) International Journal of Computer Science and Information Technologies, 
Vol. 5 (3) , 2014, 3232 – 3235. ISSN:0975-9646. 
[4]. Pranay Nanda, Shamsher Singh, G.L. Saini, “A Review of Web Caching Techniques 
and Caching Algorithms for Effective and Improved Caching”. International Journal 
of Computer Applications (0975 – 8887). Volume 128 – No.10, October 2015. 
[5]. Dhawaleswar Rao.CH, “Study of the Web Caching algorithms for performance 
Improvement of the response speed”. Indian Journal of Computer Science and 
Engineering (IJCSE). ISSN : 0976-5166. Vol. 3 No. 2 Apr-May 2012. 
Điều khiển – Cơ điện tử - Truyền thông 
 N. X. Trường, H. K. Lâm, “Đề xuất thuật toán thay thế cache cung cấp dịch vụ Internet.” 60 
[6]. A. I. Vakali, “LRU-based algorithms for Web Cache Replacement”. K. Bauknecht, S. 
Kumar Madria, and G. Pernul (Eds.): EC-Web 2000, LNCS 1875, pp. 409−418, 
2000. © Springer-Verlag Berlin Heidelberg 2000. 
[7]. Stefan Podlipnig and Laszlo Boszormenyi, “A Survey of Web Cache Replacement 
Strategies”. Institute of Information Technology, University Klagenfurt, 
Universitatsstrasse 65-67, A-9020 Klagenfurt, Austria, ACM Computing Surveys, 
Vol. 35, No. 4, December 2003, pp. 374–398. 
[8]. Vinit A. Kakde et al. “Survey of Effective Web Cache Algorithm”. International 
Journal of Science and Engineering Investigations. vol. 1, issue 2, March 2012. Paper 
ID: 10212-16. 
[9]. Arun Pasrija, “Survey on Improving the Performance of Web by Evaluation of Web 
Prefetching and Caching Algorithms”. International Journal of Advanced Research in 
Computer Engineering & Technology (IJARCET). Volume No. 2, Issue No. 6, June 
2013. ISSN: 2278 – 1323. 
[10].Pablo Rodriguez, Christian Spanner, Ernst W.Biersack: “Web Caching Architectures: 
Hierarchical and Distributed Caching”.  (4th 
International WWW Caching Workshop), Institut EUROCOM, france, 1999. 
[11]. Ho Khanh Lam, Nguyen Xuan Truong, “Performance Analysis of Hybrid Web 
Caching Architecture”, American Journal of Networks and Communications. Vol. 4, 
No. 3, 2015, pp. 37-43. doi: 10.11648/j.ajnc.20150403.13. 
[12]. Haohuan Fu, Pui-On Au, and Weijia Jia, “Performance Evaluations of Replacement 
Algorithms in Hierarchical Web Caching”. Q. Li, G. Wang, and L. Feng (Eds.): WAIM 
2004, LNCS 3129, pp. 176–185, 2004. © Springer-Verlag Berlin Heidelberg 2004. 
[13].George Kingsley Zipf, “Relative frequency as a determinant of phonetic change”. 
eprinted from the Havard Studies in Classical Philiology, Volume XL, 1929. 
ABSTRACT 
PROPOSING A REPLACE CACHE ALGORITHM FOR INTERNET WEB CACHING 
STRUCTURE OF INTERNET SERVICE STATION 
 Nowadays, development of Internet and high speed of mobile networks attract 
the a large number of users to access Internet though www service from personal 
computers (PCs) and mobile devices such as smart phone. Some Internet structures 
such as web caching [1], web caching techniques [2] and replace web cache policis 
are good solution to provide for the requirement of Internet users. Since the 1990s 
of the last century has been researched and developed many the replace web cache 
algorithms. Based on the least recently used (LRU) algorithm, a policy replace for 
the content of web cache with named LRU-EXT and evaluate the performance of 
this policy is proposed in this paper. 
LRU-EXT saves the web contents in a extend cache memory of device network, 
which was moved out of web cache by LRU algorithm. These contents will be gotten 
from themselves instead of searching in other devices of same network layer or 
higher network layer. Therefore, it can reduce the time response of web to the user. 
Keywords: Web cache, Internet web caching, Cache replacement algorithms. 
Nhận bài ngày 02 tháng 5 năm 2017 
Hoàn thiện ngày 10 tháng 6 năm 2017 
Chấp nhận đăng ngày 20 tháng 7 năm 2017 
Địa chỉ: Trường Đại học Sư phạm Kỹ thuật Hưng Yên 
 * Email: truongutehy@gmail.com