Đề 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

Đ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.” 54 
ĐỀ 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 
Nguyễn Xuân Trường*, Hồ Khánh Lâm 
Tóm tắt: Sự phát triển của Internet và các mạng thông tin di động tốc độ cao 
(3G, 4G) làm bùng nổ số lượng lớn người dùng truy nhập Internet qua WWW, 
không chỉ từ các PC, các mạng LAN mà còn từ hàng triệu thiết bị di động như 
smartphone. Các kiến trúc Internet web caching [1], các kỹ thuật Web caching [2] 
và các chính sách thay thế Web cache là những giải pháp hiệu quả kịp thời đáp ứng 
nhu cầu người dùng Internet. Từ những năm 90 của thế kỷ trước đã có nhiều thuật 
toán thay thế Web cache được nghiên cứu và phát triển. Trên cơ sở thuật toán LRU, 
trong bài báo này, chúng tôi để xuất chính sách thay thế các nội dung web cache 
được đặt tên là LRU-EXT và đánh giá hiệu năng của chính sách này. 
LRU-EXT lưu trữ những nội dung web đã được loại bỏ khỏi web cache bởi thuật 
toán LRU vào một bộ nhớ cache mở rộng ngay trong thiết bị mạng. Trong quá trình 
sử dụng, những nội dung web này sẽ được lấy ra thay vì phải tìm kiếm ở các thiết bị 
khác cùng tầng mạng hoặc ở tầng mạng cao hơn. Việc đó giúp giảm thời gian đáp 
ứng yêu cầu của người sử dụng. 
Từ khóa: Web cache, Internet web caching, Cache replacement algorithms. 
1. MỞ ĐẦU 
Web caching là lưu trữ các nội dung Web thường xuyên được người dùng tham chiếu sử 
dụng, từ đó giúp giảm sử dụng băng thông mạng, giảm trễ đáp ứng nội dung web đến người 
dùng, qua đó, tăng chất lượng dịch vụ, đặc biệt đối với sự phát triển các dịch vụ đa phương 
tiện và trực tuyến có nhu cầu băng thông cao trên Internet, và giảm các tải cho các Origin 
web server. Web caching được sử dụng ở các client (PC hay smartphone), ở các server 
(proxy server, web server, database server), Web Engine (như Cisco Web Engine), Origin 
Web server kết nối ở các cấp mạng của Internet. Càng ngày càng có nhiều nội dung web 
thông dụng, mà dung lượng nhớ của hệ thống Web caching là hữu hạn, vì vậy, cần phải loại 
bỏ những nội dung web đang được lưu trữ nhưng không còn thông dụng hay ít được tham 
chiếu. Chìa khóa của Web Caching là các thuật toán thay thế Web cache, nghĩa là loại bỏ các 
nội dung trong Web cache đã cũ hoặc được ít người dùng tham chiếu để ghi những đối 
tượng mới vào Web cache. Trong khi đó, lưu lượng trên Web tăng nhanh, tốc độ đầu tư kênh 
truyền dẫn và các tài nguyên khác trên Internet không kịp thời, thì người dùng có thể phải 
đối mặt với trễ đáp ứng của Web và lỗi dữ liệu nhiều hơn. Do đó, đưa ra các thuật toán thay 
thế Web cache hiệu quả là cần thiết cho hiệu năng Internet. Đã có một số nghiên cứu tổng 
hợp, phân loại và đánh giá các ưu nhược điểm của rất nhiều thuật toán thay thế Web cache 
[3][4][5][6][7][8][9]. Các nghiên cứu này nhóm các thuật toán thành ba loại: 
Các thuật toán thay thế cơ bản và các mở rộng của chúng: 
LRU (Least Recently Used): Thuật toán phân loại các đối tượng theo thời gian truy 
nhập gần đây nhất. Khi có trúng cache thì đối tượng được yêu cầu được đẩy về đầu của 
danh sách. Đối tượng ít được sử dụng nhất (ở cuối của danh sách) sẽ bị loại bỏ. LRU đơn 
giản để thực hiện, nhưng chỉ hiệu quả khi trong bộ nhớ cache các đối tượng là thống nhất, 
không xét đến kích thước của đối tượng. 
LFU (Least Frequently Used): Tất cả các đối tượng trong cache được phân loại theo số 
đếm lần tham chiếu. Các đối tượng có cùng số đếm được phân loại theo tính gần đây nhất, 
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 55
loại bỏ các đối tượng của Web cache ít được sử dụng. Cũng như LRU, LFU đơn giản để 
thực hiện nhưng lại không xét đến kích thước hay trễ tải các đối tượng và có thể lưu giữa 
các đối tượng không thời hạn trong cache. 
Các thuật toán dựa vào khóa: 
SIZE [Williams et al. 1996]: Phân loại các đối tượng theo kích thước. Các đối tượng có 
kích thước như nhau được phân loại theo tính tham chiếu gần đây, loại bỏ đối tượng ít 
được tham chiếu nhất gần đây và có kích thước lớn nhất. Nhược điểm là có thể lưu giữ các 
đối tượng kích thước nhỏ trong cache lâu ngay cả khi chúng không được tham chiếu 
thường xuyên gần đây, và có tỷ số trúng byte thấp (byte hit rate). Ngoài ra còn một phiên 
bản của SIZE như SIZE-LRU, SIZE-LFU, LRU-SIZE, LFU-SIZE [12]. 
LRU-MIN: Tương tự như LRU, nhưng loại bỏ đối tượng Web có kích thước nhỏ nhất. 
Nếu có một số đối tượng có kích thước nhỏ nhất thì loại bỏ đối tượng trong chúng ít được 
tham chiếu nhất gần đây. 
HLRU [Vakali 2000]: Gắn lịch sử của số tham chiếu cho đối tượng, và loại bỏ đối 
tượng có giá trị lịch sử tham chiếu nhỏ nhất. Nếu có nhiều đối tượng trong cache có giá trị 
lịch sử = 0 (nhỏ nhất), thì xét theo LRU; 
LRU-Threshold [Abrams et al. 1995]: Tương tự như LRU, nhưng đối tượng có kích 
thước lớn hơn kích thước ngưỡng không được lưu trong cache. Nó loại bỏ đối tượng dựa 
theo lịch sử tham chiếu và kích thước ngưỡng và tần số tham chiếu. 
GDS (GreedyDual-Size) [Cao and Irani, 1997]: Là mở rộng của SIZE, nó liên kết kích 
thước cho từng đối tượng Web lưu trong Cache. Khi thực hiện, GDS loại bỏ đối tượng có 
kích thước nhỏ nhất. GDS không tính đến tần số truy nhập trước đó của các đối tượng 
trong gán giá trị khóa. 
GDSF là mở rộng của GDS nhờ tính đến tần số truy nhập cho từng đối tượng trong 
Cache. Tuy vậy, GDFS không dự đoán các truy nhập tương lai. 
Các thuật toán dựa vào chi phí: 
SLRU (Size-Adjusted LRU): Chọn đối tượng có tỷ số của chi phí trên kích thước tốt 
nhất để loại bỏ. 
LRU-LSC [Hosseini-Khayat 1997]: Sử dụng danh sách LRU để xác định tính “tích 
cực” của các đối tượng trong cache. Trong quá trình thay thế, các đối tượng có tính “tích 
cực” yếu được chuyển đến danh sách thứ hai cho đến khi nào tổng kích thước của danh 
sách nhỏ hơn tổng dung lượng của cache. 
Hierarchical GreedyDual (Hierarchical GD): Thực hiện thay thế đối tượng theo GDS 
nhưng theo phân lớp. 
LFU-Aging [Arlitt et al. 2000]: Với LFU thì các đối tượng đã rất phổ dụng trong 
một quãng thời gian nào đó có thể lưu trong cache ngay cả khi chúng không được truy 
nhấp tới trong quãng thời gian dài. LFU-Aging khắc phục nhược điểm này bằng cách 
đưa vào hệ số tuổi bằng giá trị trung bình của số đếm tần số tham chiếu cho đối tượng 
và sử dụng ngưỡng. 
2. NỘI DUNG CẦN GIẢI QUYẾT 
Trong kiến trúc Web caching phân tầng (Hierarchical Web Caching) [10], 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