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 (SCPN)

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 
90 Khoa học & Công Nghệ - Số 12/Tháng 12 – 2016 Journal of Science and Technology 
ISBN 2354-0575 
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 trang các 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 trúc 
Internet web caching tối ưu về hiệu năng 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. Mô hình mạng của Internet web caching kết hợp 
Origin Servers (OC) 
Internet 
Liên kết mạng 
quốc gia – quốc tế 
Liên kết mạng khu vực- quốc gia 
Liên kết mạng khu vực - địa 
phương 
Mạng truy nhập địa phương-
Client 
ISP Central Caches (CC) 
ISP Regional Caches (RC) 
ISP Institution Caches (IC) 
Proxy caches 
Clients 
Hình 2. Mô hình cây của kiến trúc web caching phân tầng 
Mô hình cây của kiến trúc Internet web caching kết hợp cho ở 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 [7]. 
Khoa học & Công Nghệ - Số 12/Tháng 12 – 2016 Journal of Science and Technology 91 
ISBN 2354-0575 
Client (4) IC (3) RC (2) CC (1) 
Origin Servers 
(OC) 
 D
4M Client 
D
 4 REQ 
D
3M Request toRC 
E[W3Q ] 
 I C H D
3REQ 
 D
 Content to Client E[S 3 ] 
D
2M Request to CC 
 R
C
H
E[W2Q ] 
D
D4 
E[S 2 ] 
D 
2 REQ 
Content to IC 
D
1M Request to 
E[W1Q ] 
Content to Client 
D3 
 Web Server 
Content to RC 
E[S1 ] 
D
1REQ 
D4 
E[W0Q 
] 
Content to IC 
D2 
Content to CC 
E[S 0S ] 
Content to Client 
D3 
Content to RC 
D1 
D4 
Content to IC 
D 
 2 
Content to Client 
D3 
D4 
 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 
 Tổng quát, nếu kiến trúc web caching của mạng thứ n , và phụ thuộc kích thước của nội dung 
một mạng ISP có n cấp mạng, yêu cầu HTTP của web. Với kiến trúc 4 tầng thì ta có: 
client trượt web ở cấp mạng thứ n , trúng web ở hệ D4M - thời gian trượt web cục bộ tại mạng 
thống web caching ở cấp mạng thứ i , mà n i , 
của client, thời gian này phụ thuộc vào tốc độ của 
thì đáp ứng của hệ thống web caching ở cấp mạng LAN (trong đó có proxy server) của client. Nếu 
thứ i cho yêu cầu HTTP của client sẽ bằng: 
 client là một máy tính đơn lẻ không qua LAN thì 
E[Ri ] (DnM DnREQ) (Dn 1M Dn 1REQ) ... 
(1) thời gian này có thể bỏ qua. 
(Di 1M Di 1REQ) E[Ci ] Di 1 ... Dn 1 Dn 
D4REQ – thời gian mà yêu cầu HTTP của 
Trong đó: DnM - trễ do trượt web ở cấp 
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ụ 
mạng thứ n ; DnREQ - trễ phụ thuộc băng thông thuộc vào tốc độ đường truyền kết nối client qua 
kênh truyền dẫn mà yêu cầu HTTP của client (hay 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 từ proxy server cục bộ) chuyển từ cấp mạng 
phương/cơ sở , và phụ thuộc kích thước gói yêu 
thứ n đến cấp mạng thứ n 1; Dn - trễ trả về nội cầu, trễ qua các nút mạng truy nhập trung gian của 
dung web yêu cầu cho client phụ thuộc băng thông từng khu vực như quận, huyện đến các POP. 
kênh truyền dẫn từ cấp mạng thứ n 1đến cấp 
92 Khoa học & Công Nghệ - Số 12/Tháng 12 – 2016 Journal of Science and Technology 
D4 - 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. 
DICH – 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 (D4M D4REQ ) , thời gian đáp ứng trung 
ISBN 2354-0575 
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. 
bình của hệ thống web caching ở cấp mạng 3, 3. Mô hình SCPN kiến trúc Internet web 
E(C3 ) và thời gian trả nội dung web D4 . caching 
D
 IC H
( D 
4 M D 4 REQ ) E [C 3 ] D 4 
 Mạng Petri có mầu và thời gian ngẫu nhiên 
chung SCPN (Stochastic Colored Petri Net) được 
( D 4 M 
D
 4 REQ ) E [W 3 Q ] E [ S 3 ] D 4 
 (2) định nghĩa bởi 9 bộ thông số [6]: 
( D 4 M 
D
 4 REQ ) 
 E [ N 3 Q ] 
 1 
D 4 
SCPN (P,T , A, , N , C, E, G, I ) ; trong đó: P – tập 
3 
 3 
hợp các vị trí có mầu (có đặc tính dữ liệu) được ký 
 D
RCH - đáp ứng trung bình của hệ thống web 
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 
caching ở mạng khu vực khi trúng 
RC (RC hit): thời gian) hoặc không có thời gian (kích hoạt ngay 
DRCH (D4M D4REQ ) (D3M D3REQ ) E[C2 ] D3 D4 khi thỏa mãn điều kiện các vị trí vào của chúng 
(D4 REQ D4M ) (D3REQ D3M ) E[W2Q ] E[S2 ] D3 D4 (3) đều có thẻ), được biểu diễn là các thanh chữ nhật 
(D4M D4REQ ) (D3M D3REQ ) 
 E[N2Q ] 
1 
D3 D4 
 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: 
2 
 2 
P T P A T A ; 
D
CCH 
- 
đáp ứng trung bình của hệ thống web tập hợp hữu hạn 
caching ở mạng quốc gia khi trúc CC (CC hit): 
 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 D
CCH
( D
4 M D 4 REQ ) ( D3 M 
D
3 REQ 
)( D 
2 M D2 REQ ) toán và các hàm được sử dụng trong SCPN; N- 
E[C1 ] D 2 D3 D4 
hàm nút, được xác định từ A vào trong 
( D4 REQ D 4 M ) ( D3 REQ D3 M ) 
(
D
 2 REQ D2 M ) 
P T T P ; C – hàm mầu, được xác định từ P E[W1Q ] E[S1 ] D 2 D3 D4 
( D 2 M 
D
2 REQ 
) (4) 
( D4 M D4 REQ ) ( D3 M D3 REQ ) vào trong và ánh xạ các vị trí p P vào trong 
 E[ N 1Q ] 1 các mầu trong tập hợp , được viết là 
D 2 D3 D4 
C : P; G - hàm giám sát (guard function); 1 1 
DWSH - đáp ứng trung bình của Internet quốc tế và G ánh xạ từng chuyển tiếp t T vào biểu 
web server nguồn: thức giám sát. Biểu thức giám sát phải có giá trị 
D
WSH
(D
4 M 
D
4 REQ 
) (D
3M 
D
3REQ 
) (D
2 M 
D
2 REQ 
) 
 boolean true hay false, và được viết là: 
(D1M D1REQ ) E[C0 ] D1 
D2 D3 D4 
t T: Type(G(t)) BooleanType(Var(G(t))) 
(D4 REQ D4 M ) (D3REQ D3M ) (D2 REQ D2 M ) 
Trong đó Type(Vars) chỉ tập hợp các 
(D1M D1REQ ) E[W0Q ] E[S0 ] D1 D2 D3 D4 
(5) 
Type (v) | v Vars ,Vars là 
(D4 M 
D4 REQ ) (D3M D3REQ ) (D2 M 
 D
2 REQ 
) 
kiểu tập hợp các 
E[N0Q ] 
1 
biến, Vars (G(t)) chỉ các biến sử dụng trong g(t). (D1M D1REQ ) D1 D2 D3 D4 
0 
 0 E- hàm biểu thức của cung. E ánh xạ từng 
Như vậy, trường hợp xấu nhất là không trúng web 
cung a A vào trong biểu thức E. Các kiểu của 
yêu cầu ở tất cả các cấp mạng của ISP trong quốc 
Khoa học & Công Nghệ - Số 12/Tháng 12 – 2016 Journal of Science and Technology 93 
vào và ra của các biểu thức cung phải tương ứng này đề xuất sử dụng SCPN để mô hình hệ thống 
với kiểu của các nút được nối bởi cung: web caching và phân tích hiệu năng của hệ thống 
 a A : Type(E(a)) C( p(a))MS 
 web caching; TimeNET là phần mềm được sử 
 Type(var(E(a))) 
Trong đó, p(a) là vị trí trong A(a) và C( p)MS 
dụng để mô phỏng mô hình đề xuất trên. 
Hình 2(a) là mô hình SCPN hệ thống 
là tập hợp hữu hạn các multiset. 
Internet web caching ở lớp IC và kịch bản cho rằng 
I –hàm khởi tạo. I ánh xạ từng vị trí p vào 
http client yêu cầu nội dung web có ngay ở IC, 
trong các biểu thức khởi tạo (không có các biến) 
nghĩa là có IC-hit. Vị trí client_request với 2 loại 
như rằng: 
 thẻ: thẻ 1: thể hiện loại dữ liệu không online 
p P : Type(I ( p)) C( p)MS Var(I ( p)) 
(non_online_data) và thẻ 2: thể hiện loại dữ liệu 
online (online_data). Hình 2(b) và (c) là kết quả 
Đối với chuyển tiếp có thời gian, khi được xác địnhcác thông số T_non_online và T_online = 
phép (nếu các vị trí vào của nó đều có thẻ), nó bắt (số lượng truy nhập IC)/(trễ trung bình ở cấp mạng 
đầu kích hoạt, lấy các thẻ ra khỏi các vị trí vào. IC)theoms (tọa độ Y) vàchạy trong khoảng 9 
Tuy nhiên các thẻ chỉ được đưa vào các vị trí ra seconds với số lần kích hoạt thể hiện số yêu cầu 
của chuyển tiếp ngay khi trễ kết thúc. Các thẻ bị web từ client (tọa độ X) đối với non_online_data 
“giữ trong chuyển tiếp” trong khoảng trễ kích hoạt. và online_data. 
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 
(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 
94 Khoa học & Công Nghệ - Số 12/Tháng 12 – 2016 Journal of Science and Technology 
(a) 
ISBN 2354-0575 
ISBN 2354-0575 
(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) 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 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 (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. Phân tích và 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 
Khoa học & Công Nghệ - Số 12/Tháng 12 – 2016 Journal of Science and Technology 95 
ISBN 2354-0575 
dung web yêu cầu là nhỏ nhất. Với hai cấp 
webcaching 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. 
[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. 2015; 4(3): 37-43.Published 
online April 24, 2015 ( doi: 
10.11648/j.ajnc.20150403.13.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. 
96 Khoa học & Công Nghệ - Số 12/Tháng 12 – 2016 Journal of Science and Technology 
ISBN 2354-0575 
ANALYSIS PERFORMANCE OF INTERNET WEB CACHING BASED ON USED PETRI 
NETWORK MODEL HAS COLORS AND RONDOM TIME (SCPN) 
Abstract: 
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).