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