Phân tích hiệu năng của kiến trúc Internet Web Caching nhờ sử dụng mô hình mạng petri có màu và thời gian ngẫu nhiên

Nếu hệ thống IC có nội dung mà client yêu cầu (IC hit) thì IC chuyển nội dung 
yêu cầu về cho client (đồng thời Proxy server cục bộ cũng lưu nội dung trang Web 
này). Khi trượt IC (IC miss) nghĩa là nội dung trang Web mà client yêu cầu không 
có tại hệ thống IC, thì từ hệ thống IC yêu cầu được chuyển lên mạng cấp trên - mạng 
khu vực. Tại mạng khu vực, nếu hệ thống RC có nội dung yêu cầu (RC hit) thì nó 
chuyển nội dung về hệ thống IC, từ hệ thống IC chuyển tiếp về Proxy server và 
client. Nếu trượt RC (RC miss), yêu cầu của client được chuyển lên hệ thống CC của 
mạng quốc gia. Nếu hệ thống CC có nội dung thì nội dung (CC hit) được chuyển về 
hệ thống RC, rồi hệ thống IC, và đến Proxy server, đến client. Nếu trượt CC (CC 
miss), yêu cầu từ client được chuyển đến Internet quốc tế, đến Web server gốc. 
Đã có nhiều nghiên cứu tập trung vào cải thiện hiệu năng của Web dựa trên các 
thuật toán thay thế các trang Web và các giải pháp Web caching. Các yêu cầu nội 
dung Web từ người dùng phải được đáp ứng với trễ nhỏ nhất ở các tầng mạng. Đáp 
ứng nhanh nhất đối với các yêu cầu truy nhập Web phụ thuộc vào các xác suất 
trúng cache (hit rate). Nhưng khi yêu cầu các trang Web không có ở tầng mạng thì 
các yêu cầu phải được chuyển lên tầng mạng trên, như vậy trễ đáp ứng còn phụ 
thuộc cả vào các liên kết truyền thông giữa các tầng mạng. Do đó, để có một kiến 
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, 12 - 2017 155
trúc Internet Web caching tối ưu về hiệu năng sẽ dựa trên hai thông số: Trễ đáp 
ứng và chi phí băng thông kênh truyền dẫn. Bài báo này đưa ra phương pháp phân 
tích hiệu năng của kiến trúc Internet Web caching dựa trên mạng Petri [6]. 
2. NỘI DUNG CẦN GIẢI QUYẾT 
Trên cơ sở kiến trúc Internet Web caching kết hợp ở hình 1; Mô hình cây của 
kiến trúc Web caching kết hợp ở hình 2 và hình 3 là đồ thị diễn giải các trễ mà yêu 
cầu HTTP từ các client đến các Web servers trên mạng Internet với kiến trúc 
Internet Web caching kết hợp [7] ta xây dựng lý thuyết và mô hình SCPN kiến trúc 
Internet Web caching để phân tích hiệu năng của hệ thống qua các thông số trễ đáp 
ứng và chi phí băng thông kênh truyền dẫn. 
2.1. Mô hình mạng của Internet web caching kết hợp 
Hình 2. Mô hình cây của kiến trúc web caching kết hợp. 
Tổng quát, nếu kiến trúc Web caching của một mạng ISP có n cấp mạng, yêu 
cầu HTTP của client trượt Web ở cấp mạng thứ n , trúng Web ở hệ thống Web 
caching ở cấp mạng thứ i , mà n i , thì đáp ứng của hệ thống Web caching ở cấp 
mạng thứ i cho yêu cầu HTTP của client sẽ bằng: 
1 1
1 1 1 1
[ ] ( ) ( ) ...
( ) [ ] ...
i nM nREQ n M n REQ
i M i REQ i i n n
E R D D D D
D D E C D D D
(1) 
Trong đó: nMD - Trễ do trượt Web ở cấp mạng thứ n ; nREQD - Trễ phụ thuộc 
băng thông kênh truyền dẫn mà yêu cầu HTTP của client (hay từ proxy server cục 
bộ) chuyển từ cấp mạng thứ n đến cấp mạng thứ 1 n ; nD - trễ trả về nội dung 
Web yêu cầu cho client phụ thuộc băng thông kênh truyền dẫn từ cấp mạng 
thứ 1 n đến cấp mạng thứ n , và phụ thuộc kích thước của nội dung Web. Với kiến 
trúc 4 tầng thì ta có: 
MD4 - Thời gian trượt Web cục bộ tại mạng của client, thời gian này phụ thuộc 
vào tốc độ của LAN (trong đó có proxy server) của client. Nếu client là một máy 
tính đơn lẻ không qua LAN thì thời gian này có thể bỏ qua. 
Công nghệ thông tin 
N. X. Trường, H. K. Lâm, N. M. Quý, “Phân tích hiệu năng của  thời gian ngẫu nhiên.” 156 
REQD4 - Thời gian mà yêu cầu HTTP của client được gửi đến mạng địa 
phương/cơ sở (đến POP hoặc đến Router cơ sở). Thời gian này phụ thuộc vào tốc 
độ đường truyền kết nối client qua mạng truy nhập (dial-up, ADSL, vô tuyến, di 
động, đường truyền trực tiếp) tới các nút mạng địa phương/cơ sở , và phụ thuộc 
kích thước gói yêu cầu, trễ qua các nút mạng truy nhập trung gian của từng khu 
vực như quận, huyện đến các POP. 
4D - Trễ trả về client khi trúng Web ở hệ thống IC (trúng Web ở cấp 3), phụ 
thuộc vào băng thông kênh truyền dẫn và kích thước nội dung Web trả về từ cấp 
mạng địa phương đến client ở mạng cấp 4. 
ICHD - Thời gian đáp ứng trung bình của hệ thống Web caching IC khi trúng 
Web ở IC (IC hit). Thời gian này bao gồm: thời gian tổng thời gian 
)( 44 REQM DD , thời gian đáp ứng trung bình (TB) của hệ thống Web caching ở 
cấp mạng 3, )( 3CE và thời gian trả nội dung Web 4D . 
Hình 3. Đồ thị thời gian trễ của giao dịch HTTP của client trên mạng Internet 
với kiến trúc Web caching kết hợp. 
4
33
3
44
43344
4344
1][
)( 
][][)( 
][)(
D
NE
DD
DSEWEDD
DCEDDD
Q
REQM
QREQM
REQMICH
 
(2) 
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, 12 - 2017 157
RCH
D - Đáp ứng TB của hệ thống Web caching ở mạng khu vực khi trúng RC 
(RC hit): 
43
22
2
3344
43223344
4323344
1][
)()(
][][)()(
][)()(
DD
NE
DDDD
DDSEWEDDDD
DDCEDDDDD
Q
REQMREQM
QMREQMREQ
REQMREQMRCH
 
(3) 
CCHD - Đáp ứng TB của hệ thống Web caching ở mạng quốc gia khi trúc CC 
(CC hit): 



432
11
1
223344
43211
223344
4321
223344
1][
)()()(
][][
)()()(
][
)()()(
DDD
NE
DDDDDD
DDDSEWE
DDDDDD
DDDCE
DDDDDDD
Q
REQMREQMREQM
Q
MREQMREQMREQ
REQMREQMREQMCCH
 
(4) 
WSHD - Đáp ứng trung bình của Internet quốc tế và Web server nguồn: 



4321
00
0
11
223344
43210011
223344
4321011
223344
1][
)( 
)()()(
][][)( 
)()()(
][)( 
)()()(
DDDD
NE
DD
DDDDDD
DDDDSEWEDD
DDDDDD
DDDDCEDD
DDDDDDD
Q
REQM
REQMREQMREQM
QREQM
MREQMREQMREQ
REQM
REQMREQMREQMWSH
 
(5) 
Như vậy, trường hợp xấu nhất là không trúng Web yêu cầu ở tất cả các cấp 
mạng của ISP trong quốc gia và chỉ trúng Web trên cấp mạng Internet quốc tế ở 
Web server nguồn. Công thức (5) là công thức tổng quát để tính trễ truy nhập Web 
cho trường hợp xấu nhất này. Các công thức trên đây [7] cho thấy sự phụ thuộc 
vào từng hệ thống Web caching ở từng cấp mạng: Các liên kết ngang hàng, số 
lượng nút hệ thống Web caching, giao thức thay thế Web cache, các liên kết của 
các hệ thống Web caching của các tầng mạng với nhau, và số lượng tầng mạng. 
2.2. Mô hình SCPN kiến trúc Internet Web caching 
Mạng Petri có mầu và thời gian ngẫu nhiên chung SCPN được định nghĩa bởi 9 
bộ thông số [6]: ),,,,,,,,(  IGECNATPSCPN ; Trong đó: P – Tập hợp các vị trí có 
mầu (có đặc tính dữ liệu) được ký hiệu bằng các vòng tròn với các thẻ (dấu chấm 
đen); T – Tập hợp các chuyển tiếp (có thể là hàm thời gian) hoặc không có thời 
gian (kích hoạt ngay khi thỏa mãn điều kiện các vị trí vào của chúng đều có thẻ), 
được biểu diễn là các thanh chữ nhật trắng (có thời gian) hoặc thanh đen (không có 
thời gian); A tập hợp các cung thỏa mãn: ;    ATAPTP  Tập hợp hữu 
hạn của các tập hợp mầu xác định trong SCPN. Tập hợp này chứa tất cả các mầu 
có thể thể, các phép toán và các hàm được sử dụng trong SCPN; N- Hàm nút, được 
xác định từ A vào trong PTTP  ; C – Hàm mầu, được xác định từ P vào trong 
 và ánh xạ các vị trí Pp vào trong các mầu trong tập hợp Ʃ, được viết là 
:C P Ʃ; G - Hàm giám sát (guard function); 
G ánh xạ từng chuyển tiếp Tt vào biểu thức giám sát. Biểu thức giám sát 
phải có giá trị boolean true hay false, và được viết là: 
Công nghệ thông tin 
N. X. Trường, H. K. Lâm, N. M. Quý, “Phân tích hiệu năng của  thời gian ngẫu nhiên.” 158 
   )))((())((: tGVarTypeBooleantGTypeTt . Trong đó, )(VarsType chỉ tập hợp 
các kiểu VarsvvType |)( ,Vars là tập hợp các biến, ))(( tGVars chỉ các biến sử 
dụng trong g(t). 
E - Hàm biểu thức của cung. E ánh xạ từng cung Aa vào trong biểu thức E. 
Các kiểu của vào và ra của các biểu thức cung phải tương ứng với kiểu của các nút 
được nối bởi cung:    )))((var())(())((: aETypeapCaETypeAa MS . Trong đó, )(ap 
là vị trí trong )(aA và MSpC )( là tập hợp hữu hạn các multiset. 
I – Hàm khởi tạo. I ánh xạ từng vị trí p vào trong các biểu thức khởi tạo (không 
có các biến) như rằng:     ))(()())((: pIVarpCpITypePp MS . 
Đối với chuyển tiếp có thời gian, khi được phép (nếu các vị trí vào của nó đều 
có thẻ), nó bắt đầu kích hoạt, lấy các thẻ ra khỏi các vị trí vào. Tuy nhiên, các thẻ 
chỉ được đưa vào các vị trí ra của chuyển tiếp ngay khi trễ kết thúc. Các thẻ bị “giữ 
trong chuyển tiếp” trong khoảng trễ kích hoạt. 
3. MÔ PHỎNG, TÍNH TOÁN 
Kết quả nghiên cứu trong [7], [8] có đề xuất sử dụng mạng hàng đợi để phân tích 
hiệu năng của kiến trúc Internet Web caching kết hợp. Bài báo này đề xuất sử dụng 
SCPN để mô hình hệ thống Web caching và phân tích hiệu năng của hệ thống Web 
caching; TimeNET là phần mềm được sử dụng để mô phỏng mô hình đề xuất trên. 
(a) 
(b) 
(c) 
Hình 4. (a) Mạng SCPN của cấp webching cache IC khi có IC-hit; 
(b) Trễ nhận nội dung Web với non-online-data; 
(c)Trễ nhận nội dung Web với online-data. 
Hình 4 (a) là mô hình SCPN hệ thống Internet Web caching ở lớp IC và kịch 
bản cho rằng http client yêu cầu nội dung Web có ngay ở IC, nghĩa là có IC-hit. Vị 
trí client_request với 2 loại thẻ, thẻ 1: Thể hiện loại dữ liệu không online 
(non_online_data) và thẻ 2: Thể hiện loại dữ liệu online (online_data). Hình 4(b) 
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, 12 - 2017 159
và (c) là kết quả xác định các thông số T_non_online và T_online = (số lượng truy 
nhập IC)/(trễ trung bình ở cấp mạng IC) theo tọa độ Y và chạy trong khoảng 9 
seconds với số lần kích hoạt thể hiện số yêu cầu Web từ client (tọa độ X) đối với 
non_online_data và online_data. 
(a) 
(b) 
(c) 
(d) 
Hình 5. (a) Mạng SCPN của hai cấp webching cache IC-RC 
khi có IC-miss và RC-hit; (b) Mạng SCPN con cho RC; 
(c) Trễ nhận nội dung web với non-online-data; 
(d) Trễ nhận nội dung web với online-data. 
Hình 5 (a) là mô hình SCPN hệ thống Internet hai cấp web caching IC-RC khi 
IC-miss và RC-hit, trong đó, vị trí RC-request thể hiện mô hình SCPN con cho RC 
Công nghệ thông tin 
N. X. Trường, H. K. Lâm, N. M. Quý, “Phân tích hiệu năng của  thời gian ngẫu nhiên.” 160 
(hình 5(b)). Hình 5(c) và (d) là kết quả xác định các thông số 
T_non_online_IC_to_RC và T_online_IC_to_RC = (số lượng truy nhập IC)/(tổng 
trễ trung bình của cấp mạng IC và RC) theo ms (tọa độ Y) và chạy trong khoảng 
64 seconds với số lần kích hoạt thể hiện số yêu cầu web từ client (tọa độ X) đối với 
non_online_data và online_data. 
Có thể bằng cách tương tự xác định được các mô hình SCPN cho hệ thống 3 cấp 
Web caching IC-RC-CC khi có IC-miss, RC-miss, CC-hit, và hệ thống 4 cấp Web 
caching IC-RC-CC-OC khi IC-miss, RC-miss, CC-miss, và OC-hit. 
4. KẾT LUẬN 
Với một cấp Web caching, ví dụ IC (hình 4), kết quả mô phỏng phụ thuộc vào 
số yêu cầu Web từ client và trễ trung bình ở các cấp Web caching. Đối với dữ liệu 
online, thông thường có độ dài lớn nên chúng có chi phí trễ trung bình lớn hơn so 
với dữ liệu non-online (thể hiện ở các thông số đặt trước trên các hình 4(a) và 
5(a)). Do đó, thông số hiệu năng T_online < T_non_online nhận được nội dung 
Web yêu cầu là nhỏ nhất. Với hai cấp Web caching IC-RC khi IC không sẵn sàng 
nội dung (vị trí IC_content_not_ready có thẻ) kết quả mô phỏng ở hình 5(c) và (d) 
cho thấy ban đầu vì tỷ số IC-miss và nội dung web cần được lấy từ cấp RC với trễ 
truy nhập lớn nên giá trị T_online_IC_to_RC < T_online_IC và 
T_non_online_IC_to_RC < T_non_online. Với sự tăng số thể từ RC đến vị trí 
IC_web_content_ready, tỷ số IC_hit cao lên, do đó, trễ truy nhập giảm, khi đó, 
T_online_IC_to_RC > T_online_IC và T_non_online_IC_to_RC > T_non_online. 
Như vậy, với số cấp Web caching tăng ta có thể giảm trễ truy nhập Internet, trong 
khi không cần phải tăng dung lượng băng thông của từng cấp mạng. 
Với phương pháp mô hình hóa bằng SCPN và đưa vào các đặc tính về dữ liệu 
cho các loại thẻ trong các vị trí như mức ưu tiên, độ dài dữ liệu (hay số lượng các 
gói tin), và thay đổi các thông số về trễ trung bình của các cấp mạng Web caching, 
ta có thể xác định các thông số hiệu năng khác để đánh giá hiệu năng của kiến trúc 
Internet Web caching. 
TÀI LIỆU THAM KHẢO 
[1]. Carey Williamson, Mudashiru Busari: “Simulation Evaluation of Web 
Caching Architectures”, M.Sc. Thesis, June 2000, Department of Computer 
science, University of Saskatchewan,  
[2].Haohuan Fu, Pui-On Au, Weijia Jia, 2004. “Performance Evaluation of 
Replacement Algorithms In Hierarchical Web Caching”. Book series Lecture 
notes in computer science, Publisher Springer Berlin/Heidelberg, ISSN 0302-
9743(print) 1611-3349 (online), volume 3129/2004. 
[3]. A. Rousskov, “On Performance of Caching Proxies”, In ACM 
SIGMETRICS, Madison, USA, September 1998. 
[4]. C. Maltzahn, J.Richardson, “Performance Issues of Enterprise Level Web 
Proxies”, 1998 
[5]. M. Deshpande, G. Karypis, “Selective Markov models for pedicting Web page 
access”. ACM Transactions on Internert technology, May 2004. 
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, 12 - 2017 161
[6]. Hồ Khánh Lâm, “Mạng Petri: lý thuyết và ứng dụng". Trường Đại học Sư 
phạm Kỹ thuật Hưng Yên, NXB KHKT, 2015. 
[7]. 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. ISSN: 2326-893X (Print); ISSN: 2326-8964 
(Online). 
[8]. Hồ Khánh Lâm, Nguyễn Xuân Trường, "Sử dụng mạng hàng đợi phân tích 
ảnh hưởng của các client proxy server trong kiến trúc web caching". Tạp chí 
Khoa học và Công nghệ - Đại học Thái Nguyên Tập 137, số 07, 2015. ISSN: 
1859 - 2171. 
ABSTRACT 
ANALYSIS PERFORMANCE OF INTERNET WEB CACHING 
BASED ON USED PETRI NETWORK MODEL HAS COLORS 
AND RONDOM TIME (SCPN) 
At present, the communication network technology developed rapidly 
provide high speed multimedia services to serve the demand of web 
services's users. Web caching is an application-level routing and bandwidth 
for most of the web with the goalsare increasing the line speed and the web 
access speed. Currently, there are several different methods to evaluate the 
performance of internet web caching architecture. However, modeling 
methods use colored Petri network and random time (SCPN) is a completely 
new method helps to identify and adjust parameters to optimize performance 
of internet web caching architecture based on two parameters: delay and 
cost to meet the transmission bandwidth channel. This paper gives a method 
for analyzing the performance of Internet web caching architecture oriented 
based approach Petri net aims to optimize web caching architecture to 
improve web access speed and use multimedia services on the internet. 
Keywords: Web caching, Petri network (PN), Petri network model has colors and random time (SCPN). 
Nhận bài ngày 16 tháng 8 năm 2017 
Hoàn thiện ngày 26 tháng 11 năm 2017 
Chấp nhận đăng ngày 28 tháng 11 năm 2017 
Địa chỉ: Trường Đại học Sư phạm Kỹ thuật Hưng Yên. 
 * Email: truongutehy@gmail.com.