Đánh giá hiệu năng của thuật toán thay thế web cache lru - Ext cho Internet Web caching sử dụng mạng tích hợp hàng đợi và petri net có thời gian

c san CNTT, 11 - 2018 147
Hình 3. Mô hình mạng 4 cấp cache tìm đối tượng web 
và thực hiện thay thế web cache. 
2.2. Mô hình với ba cấp cache 
 Để so sánh kiến trúc Web caching giữa ba cấp và bốn cấp cache, chúng tôi đưa 
vào mô hình ba cấp cache như ở hình 4. 
Hình 4. Mô hình mạng 3 cấp cache tìm đối tượng Web 
và thực hiện thay thế Web Cache. 
2.3. Mô hình mạng tích hợp cho phân tích kiến trúc cache với thực hiện thay 
thế web cache bằng LRU-EXT 
Hình 5. Mô hình tích hợp kiến trúc cache với thực hiện t 
hay thế Web cache bằng LRU-EXT. 
Công nghệ thông tin 
N. X. Trường, H. K. Lâm, N. M. Quý, “Đánh giá hiệu năng  và Petri Net có thời gian.” 148 
Từ đồ thị diễn giải thực hiện thuật toán thay thế Web cache ở hình 2, chúng tôi đề 
xuất mô hình mạng tích hợp hàng đợi và GSPN của kiến trúc Web caching 3 cấp ở 
hình 5. 
Bảng 2. Các nút của mô hình cho ở hình 5. 
Mạng GSPN 
Các nút Chức năng Các nút Chức năng 
Client-D Yêu cầu client http L2-NoMinSize Min Size In Cache L2: No 
PRC-L0-S Ghi vào Cache L0 L0-NoMaxSize Max Size IN Cache L0: No 
PRC-L0-H Trúng Cache L0 L1-NoMaxSize Max Size IN Cache L1: No 
PRC-L0-M Trượt Cache L0 L2-NoMaxSize Max Size IN Cache L2: No 
PRC-L0-
FULL 
Cache L0 đã đầy tReq_L0 Client request to Proxy Server 
Cache L0 
PRC-L1-S Ghi vào Cache L1 tL0Resp Đáp ứng trả về client từ Cache 
L0 
PRC-L1-H Trúng Cache L1 tReq_L1 Gửi yêu cầu đến Proxy Server 
Cache L1 
PRC-L1-M Trượt Cache L1 tL1Resp Đáp ứng trả về Cache L0 từ 
Cache L1 
PRC-L1-
FULL 
Cache L1 đã đầy tReq_L2 Gửi yêu cầu đến Proxy Server 
Cache L2 
PRC-L2-S Ghi vào Cache L2 tL2Resp Đáp ứng trả về Cache L1 từ 
Cache L2 
PRC-L2-H Trúng Cache L2 tReq_OS Gửi yêu cầu đến Origin Server 
Cache 
PRC-L2-M Trượt Cache L2 tOSResp Đáp ứng trả về Cache L2 từ 
Cache OS 
PRC-L2-
FULL 
Cache L2 đã đầy tSizeCompLRU
MINL0 
SIZE Compare: New Object 
and Cache L0 Object by LRU-
MIN 
ORG-H Trúng Cache ORG tSizeCompLRU
MINL1 
SIZE Compare: New Object 
and Cache L1 Object by LRU-
MIN 
L0-
YesMinSize 
Min Size In Cache 
L0: Yes 
tSizeCompLRU
MINL2 
SIZE Compare: New Object 
and Cache L2 Object by LRU-
MIN 
L1- Min Size In Cache tStoreIntoLEWC Store Object to Ext Cache L0 
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 CNTT, 11 - 2018 149
YesMinSize L1: Yes -L0 
L2-
YesMinSize 
Min Size In Cache 
L2: Yes 
tStoreIntoLEWC
-L1 
Store Object to Ext Cache L1 
L0-
YesMaxSize 
Max Size In Cache 
L0: Yes 
tStoreIntoLEWC
-L2 
Store Object to Ext Cache L2 
L1-
YesMaxSize 
Max Size In Cache 
L1: Yes 
tSizeCompSIZEI
nL0 
SIZE Compare: New Object 
and Cache L0 Object by SIZE 
L2-
YesMaxSize 
Max Size In Cache 
L1: Yes 
tSizeCompSIZEI
nL0 
SIZE Compare: New Object 
and Cache L1 Object by SIZE 
L0-
NoMinSize 
Min Size In Cache 
L0: No 
tSizeCompSIZEI
nL0 
SIZE Compare: New Object 
and Cache L2 Object by SIZE 
L1-
NoMinSize 
Min Size In Cache 
L1: No 
Mạng Hàng đợi 
Các nút Chức năng Các nút Chức năng 
Client-Q Các đầu cuối người 
dùng 
PRC-OS-L2-W Ghi đối tượng Web từ Cache 
OS vào L2 
PRC-L0 Proxy Server Cache 
L0 
PRC-L0-
MinSizeFind 
Min Size finded in Cache L0 
PRC-L1 Proxy Server Cache 
L1 
PRC-L1-
MinSizeFind 
Min Size finded in Cache L1 
PRC-L2 Proxy Server Cache 
L2 
PRC-L2-
MinSizeFind 
Min Size finded in Cache L2 
OrgSER Origin Server PRC-L0-
MaxSizeFind 
Max Size finded in Cache L0 
PRC-L1-L0-
W 
Ghi đối tượng Web 
từ Cache L1 vào L0 
PRC-L1-
MaxSizeFind 
Max Size finded in Cache L1 
PRC-L2-L1-
W 
Ghi đối tượng Web 
từ Cache L2 vào L1 
PRC-L2-
MaxSizeFind 
Max Size finded in Cache L2 
3. MÔ PHỎNG, TÍNH TOÁN 
3.1. So sánh các kiến trúc Web caching 4 cấp cache, 3 cấp cache với thực hiện 
thay thế Web cache, và thực hiện LRU-EXT 
 - Sử dụng công cụ JMT1.0.2 tính các thông số hiệu năng: PRC-
L0_class1_Number of Customers (j): Số yêu cầu của client đến Proxy Server 
Cache 
Công nghệ thông tin 
N. X. Trường, H. K. Lâm, N. M. Quý, “Đánh giá hiệu năng  và Petri Net có thời gian.” 150 
PRC-L0_class1_Response Time (s): Đáp ứng của Proxy Server Cache L0 (giây) 
PRC-L0_class1_Utilization: Mức độ sử dụng của Proxy Server Cache L0 
class1_Systen Number of Customers (j): Tổng số yêu cầu http trong kiến trúc 
mạng 
class1_System Response Time (s): Đáp ứng trung bình của kiến trúc mạng 
3.2. Mô phỏng 
 a) Đặt thời gian phục vụ của các nút hàng đợi mô hình mạng 4 cấp cache cho ở 
hình 3: PRC-L0, PRC-L1-L0-W, PRC-L1, PRC-L2, PRC-L2-L1-W, PRC-L3, 
PRC-L3-L2-W, PRC-OS-L3-W, OrgSER có phân bố mũ f(x)=λe-λx và có giá trị 
trung bình= 0.25s và λ=4. 
 Các chuyển tiếp có thời gian trễ kích hoạt như sau: tReq_L0=1s mean và λ=1; 
tL0Resp=4s mean và λ=0.25; tReq_L1 = 5s mean và λ=0.2; tL1Resp=10s mean và 
λ=0.1; tReq_L2=8s mean và λ=0.125; tL2Resp=15s mean và λ=0.067; 
tReq_L3=10s mean và λ=0.1; tL3Resp=20s mean và λ=0.05; tReq_OS=15s mean 
và λ=0.067; tOSResp=25s mean và λ=0.04; 
tReplL0=tReplL1=tReplL2=tReplL3=0.2s mean và λ=5. 
 b) Đặt thời gian phục vụ của các nút hàng đợi mô hình mạng 3 cấp cache cho ở 
hình 4: PRC-L0, PRC-L1-L0-W, PRC-L1, PRC-L2, PRC-L2-L1-W, PRC-OS-L2-
W, OrgSER có phân bố mũ f(x)=λe-λx và có giá trị trung bình = 0.25 và λ=4. Các 
chuyển tiếp có thời gian trễ kích hoạt như sau: tReq_L0=1s mean và λ=1; 
tL0Resp=4s mean và λ=0.25; tReq_L1=5s mean và λ=0.2; tL1Resp=10s mean và 
λ=0.1; tReq_L2=8s mean và λ=0.125; tL2Resp=15s mean và λ=0.067; 
tReq_OS=15s mean và λ=0.067; tOSResp=25s mean và λ=0.04; 
tReplL0=tReplL1=tReplL2=tReplL3=0.2s mean và λ=5. 
 c) Đặt thời gian phục vụ của các nút hàng đợi mô hình mạng 3 cấp cache những 
có thực hiện LRU-EXT cho ở hình 5: PRC-L0, PRC-L1-L0-W, PRC-L1, PRC-L2, 
PRC-L2-L1-W, PRC-OS-L2-W, OrgSER có phân bố mũ f(x)=λe-λx và có giá trị 
trung bình = 0.25 và λ=4. Các nút hàng đợi L0-MaxSizeFind, PRC-L0-
MinSizeFind, L1-MaxSizeFind, PRC-L1-MinSizeFind, L2-MaxSizeFind, và PRC-
L2-MinSizeFind có thời gian phục vụ trung bình = 0.2s và λ=5. Các chuyển tiếp có 
thời gian trễ kích hoạt như sau: tReq_L0=1s mean, λ=1; tL0Resp=4s mean, 
λ=0.25; tReq_L1= 5s mean, λ=0.2; tL1Resp=10s mean, λ=0.1; tReq_L2=8s mean, 
λ=0.125; tL2Resp=15s mean, λ=0.067; tReq_OS=15s mean, λ=0.067; 
tOSResp=25s mean, λ=0.04; tReplL0=tReplL1=tReplL2=tReplL3=0.2s mean, 
λ=5. Các chuyển tiếp tức thời cho thực hiện LRU-EXT: tSizeCompLRUMINInL0, 
tStoreIntoLEWC-L0, L0-YesMinSizeFind, L0-MaxSizeFind, 
tSizeCompLRUMINInL1, tStoreIntoLEWC-L1, L1-YesMinSizeFind, L1-
MaxSizeFind, tSizeCompLRUMINInL2, tStoreIntoLEWC-L2, L2-
YesMinSizeFind, và L2-MaxSizeFind. 
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 CNTT, 11 - 2018 151
 d) Xác suất định tuyến của các hàng đợi được xác định cho trường hợp có xác 
suất trúng cache cao: PRC-Li-H = 0.9, PRC-Li-M = 0.1; trong đó, i = 0, 1, 2, 3 
 Để có thể thực hiện thay thế Web cache, đặt trường hợp xấu nhất: PRC-L0-L0-
W có xác suất định tuyến đến nút vị trí PRC-Li-FULL = 0.9; trong đó i = 0, 1, 2, 3 
3.3. Kết quả chạy mô phỏng các mô hình mạng 
 a) Mạng 4 cấp cache: b) Mạng 3 cấp cache: 
Hình 6a. PLC-L0_class1_Number of 
Customers (j). 
Hình 7a. PLC-L0_class1_Number of 
Customers (j). 
Hình 6b. PRC-L0_class1_Response 
Time (s). 
Hình 7b. PRC-L0_class1_Response 
Time (s). 
Hình 6c. PRC-L0_class1_Utilization. 
Hình 7c. PRC-L0_class1_Utilizatio. 
Hình 6d. class1_System Number of 
Customers (j). 
Hình 7d. class1_System Number of 
Customers (j). 
Công nghệ thông tin 
N. X. Trường, H. K. Lâm, N. M. Quý, “Đánh giá hiệu năng  và Petri Net có thời gian.” 152 
Hình 6e. class1_System Response 
Time (s). 
Hình 7e. class1_System Response Time 
(s). 
 c) Mạng 3 cấp cache với thuật toán thay thế Web cache LRU-EXT 
Hình 8a. PLC-L0_class1_Number of 
Customers (j). 
Hình 8b. PRC-L0_class1_Response 
Time (s). 
Hình 8c. PRC-L0_class1_Utilization. 
Hình 8d. class1_System Number of 
Customers (j). 
Hình 8e. class1_System Response Time (s). 
3.4. Đánh giá kết quả 
 Vì Proxy Server L0 nằm ngay tại mạng của người dùng Internet, nó ảnh hưởng 
trực tiếp và quan trọng đến chất lượng đáp ứng các yêu cầu http từ người dùng, nên 
các số đo hiệu năng lấy trên PRC-L0. Mạng 4 cấp cache và mạng 3 cấp cache sử 
dụng thay thế Web cache cho thấy đáp ứng của PRC-L0_Response Time (s) có sự 
khác nhau. Giá trị này của mạng 3 cấp cache (3.393s-232.768s) nhỏ hơn so với 
mạng 4 cấp cache (3.658s-241.543s), đó là vì trễ đáp ứng của mạng 4 cấp cache có 
cao hơn, trong khi xác suất trúng cache cục bộ được đặt giống nhau. Đáp ứng của 
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 CNTT, 11 - 2018 153
hệ thống mạng 3 cấp cache (662.241s-2050.199s) có giá trị trung bình tương 
đương với mạng 4 cấp cache (667.894s-1879.915s). Điều này xác định số cấp 
cache khác nhau của kiến trúc Web caching không ảnh hưởng nhiều đến đáp ứng 
của mạng cho các yêu cầu người dùng (http client). 
 Kết quả mô phỏng của mô hình mạng 3 cấp cache có thực hiện thuật toán thay 
thế được đề xuất LRU-EXT cho thấy PRC-L0-class1_Response Time (s) (3.111s-
230.901s) nhỏ hơn kết quả của mạng 3 cấp cache không sử dụng LRU-EXT 
(3.393s-232.768s). Đáp ứng của hệ thống với LRU-EXT (507.463s-1870.567s) 
cũng nhỏ hơn hệ thống không có LRU-EXT (662.241s-2050.199s). Như vậy, sự 
đưa vào thuật toán LRU-EXT vừa đảm bảo có được truy nhập các nội dung web 
lịch sử vừa cho đáp ứng trung bình của Proxy Server Cache và toàn kiến trúc mạng 
có nhúng thuật toán LRU-EXT tốt hơn. 
4. KẾT LUẬN 
 Sự kết hợp mạng hàng đợi và mạng Petri có thời gian cho phép thực hiện mô 
hình hóa các kiến trúc mạng và các thuật toán phức tạp. Sử dụng mô hình kết hợp 
này chúng tôi đã có thể phân tích và đánh giá hiệu năng thuật toán thay thế Web 
cache LRU-EXT được đề xuất mà nghiên cứu [1] đã trình bày. Công nghệ nhớ làm 
cho vấn đề mở rộng dung lượng của cache (trên hệ thống đĩa) của Proxy Server là 
đơn giản, vì vậy LRU-EXT sẽ làm tăng tỷ số trúng cache, tỷ số trúng byte, và giảm 
thời gian đáp ứng của Proxy Server Cache, giảm tải lưu lượng ở các cấp mạng trên 
về phía các Server nguồn của các web site. 
TÀI LIỆU THAM KHẢO 
[1]. Nguyễn Xuân Trường, Hồ Khánh Lâm, "Đề 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". Tạp 
chí Nghiên cứu Khoa học và Công nghệ quân sự, số đặc san 07-2017 (Tr. 54-
60). ISSN: 1859-1043. 
[2]. Pablo Rodriguez, Christian Spanner, Ernst W.Biersack,"Web Caching 
Architectures: Hierarchical and Distributed Caching". 
 (4th International WWW Caching Workshop), 
Institut EUROCOM, france, 1999. 
[3]. 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. 
[4]. George Kingsley Zipf, “Relative frequency as a determinant of phonetic 
change”. eprinted from the Havard Studies in Classical Philiology, Volume 
XL, 1929. 
Công nghệ thông tin 
N. X. Trường, H. K. Lâm, N. M. Quý, “Đánh giá hiệu năng  và Petri Net có thời gian.” 154 
[5]. Harshal N. Datir, Yogesh H. Gulhane, P.R. Deshmukh, "Analysis and 
Performance Evaluation of Web Caching Algorithms". International Journal 
of Engineering Science and Technology (IJEST). ISSN : 0975-5462 NCICT. 
Special Issue Feb 2011. 
[6]. Christoph Lindemann and Martin Reiser, "Modeling Web Proxy Cache 
Architectures". 
[7]. Valentina Martina, Michele Garetto, Emilio Leonardi, "A unified approach to 
the performance analysis of caching systems".https://arxiv.org/pdf/ 
 1307.6702.pdf. 2016 
[8]. Tamas Berczes, Janos Sztrik, "A queueing network model to study Proxy 
Cache Servers". Proceedings of the 7th International Conference on Applied 
Informatics Eger, Hungary, January 28–31, 2007. Vol. 1. pp. 203–210. 
[9]. Xue Liu, Jin Heo, Lui Sha, "Modeling 3-Tiered Web Services". University of 
Illinois at Urbana-Champaign. 
[10]. TAMÁS BÉRCZES, "Performance evaluation of Proxy Cache Servers". 
University of Debrecen, Dept. of Informatics Systems and Networks. 
7/2006. 
[11]. J. Cao, M. Andersson, C. Nyberg, and M. Kihl, "Web server performance 
modeling using an M/G/1/K*PS queue”, presented at 10th International 
Conference on Telecommunications (ICT 2003), 2003. 
[12]. K. Y. Wong and K. H. Yeung, "Analytical Study on Web Caching Systems 
using Closed Queuing Network Modeling". Computer Studies Program 
Macao Polytechnic Institute. 
[13]. M.Bertoli, G.Casale, G.Serazzi, "JMT: performance engineering tools for 
system modeling". ACM SIGMETRICS Performance Evaluation Review, 
Volume 36 Issue 4, New York, US, March 2009, 10-15, ACM press. 
(Article) (BibTex). 
[14]. "CPN Tools: A tool for editing, simulating, and analyzing Colored Petri 
nets". 
[15]. Kurt Jensen, "A Brief Introduction to Coloured Petri Nets". Computer 
Science Department, University of Aarhus NyMunkegade, Bldg. 540, DK-
8000 AarhusC, Denmark. 
[16]. Reinhard German, Christian Kelling, Armin Zimmermann, Günter Hommel, 
"TimeNET: a toolkit for evaluating non-Markovian stochastic Petri nets". 
Performance Evaluation Volume 24, Issues 1–2, November 1995, Pages 69. 
[17]. "CacheSIM: A Web Cache Simulator Tool Based on Coloured Petri Nets and 
Java Programming". IEEE Latin America Transactions (Volume: 13, Issue: 
5, May 2015). Print ISSN: 1548-0992. 
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 CNTT, 11 - 2018 155
ABSTRACT 
EVALUATE PERFORMANCE OF REPLACEMENT WEB CACHE LRU-EXT 
ALGORITHM FOR INTERNET WEB CACHING USING INTEGRATED 
QUEUE NETWORK AND GENERALIZED STOCHASTIC PETRI NETS 
Web caching is to save the copy of the document web which is near to the 
web user; Web caching is the application in the routing level and the most 
bandwidth is used for web to go up speed data transfer and speed access web. 
The internet web caching architectures and web cache replacement policies 
are the importance solution and they can not missing in the internet 
development to provide the high quality services. Some algorithm of the web 
cache replacement are RLU, LFU, MRU and etc were applied since many 
years ago. Nevertheless, each algorithm exists the advantage and dis 
advantage. Therefore, web cache replacement has been considered by the 
reseacheres. The LRU-EXT algorithm web cache replacement was proposed 
[1] and its evaluated by the examples and the formular equations. In this 
paper, we propose a model which is the network integrated the queue and 
Petri net has common time to evaluate the performance of the algorithm 
LRU-EXT. 
Keywords: Internet web caching architecture; LRU-EXT; Hybrid model of Queue and GSPN. 
Nhận bài ngày 28 tháng 6 năm 2018 
Hoàn thiện ngày 03 tháng 10 năm 2018 
Chấp nhận đăng ngày 05 tháng 11 năm 2018 
Địa chỉ: Trường Đại học Sư phạm kỹ thuật Hưng Yên. 
 * Email: truongutehy@gmail.com