Đề 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<br /> <br /> ĐỀ XUẤT THUẬT TOÁN THAY THẾ CACHE<br /> CHO KIẾN TRÚC INTERNET WEB CACHING<br /> CỦA NHÀ CUNG CẤP DỊCH VỤ INTERNET<br /> Nguyễn Xuân Trường*, Hồ Khánh Lâm<br /> 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<br /> (3G, 4G) làm bùng nổ số lượng lớn người dùng truy nhập Internet qua WWW,<br /> 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ư<br /> smartphone. Các kiến trúc Internet web caching [1], các kỹ thuật Web caching [2]<br /> 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<br /> 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<br /> 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,<br /> 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<br /> được đặt tên là LRU-EXT và đánh giá hiệu năng của chính sách này.<br /> LRU-EXT lưu trữ những nội dung web đã được loại bỏ khỏi web cache bởi thuật<br /> toán LRU vào một bộ nhớ cache mở rộng ngay trong thiết bị mạng. Trong quá trình<br /> 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ị<br /> 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<br /> ứng yêu cầu của người sử dụng.<br /> Từ khóa: Web cache, Internet web caching, Cache replacement algorithms.<br /> <br /> 1. MỞ ĐẦU<br /> 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ử<br /> 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<br /> 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<br /> 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<br /> web server. Web caching được sử dụng ở các client (PC hay smartphone), ở các server<br /> (proxy server, web server, database server), Web Engine (như Cisco Web Engine), Origin<br /> 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<br /> 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<br /> 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<br /> 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<br /> nội dung trong Web cache đã cũ hoặc được ít người dùng tham chiếu để ghi những đối<br /> 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<br /> 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<br /> đố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<br /> 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<br /> 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<br /> [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:<br /> Các thuật toán thay thế cơ bản và các mở rộng của chúng:<br /> LRU (Least Recently Used): Thuật toán phân loại các đối tượng theo thời gian truy<br /> 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<br /> 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<br /> 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,<br /> không xét đến kích thước của đối tượng.<br /> LFU (Least Frequently Used): Tất cả các đối tượng trong cache được phân loại theo số<br /> đế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,<br /> <br /> <br /> <br /> 54 N. X. Trường, H. K. Lâm, “Đề xuất thuật toán thay thế cache… cung cấp dịch vụ Internet.”<br /> Nghiên cứu khoa học công nghệ<br /> 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 để<br /> 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<br /> các đối tượng không thời hạn trong cache.<br /> Các thuật toán dựa vào khóa:<br /> 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ó<br /> 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<br /> đượ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<br /> đối tượng kích thước nhỏ trong cache lâu ngay cả khi chúng không được tham chiếu<br /> 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<br /> bản của SIZE như SIZE-LRU, SIZE-LFU, LRU-SIZE, LFU-SIZE [12].<br /> LRU-MIN: Tương tự như LRU, nhưng loại bỏ đối tượng Web có kích thước nhỏ nhất.<br /> 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<br /> tham chiếu nhất gần đây.<br /> HLRU [Vakali 2000]: Gắn lịch sử của số tham chiếu cho đối tượng, và loại bỏ đối<br /> 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ị<br /> lịch sử = 0 (nhỏ nhất), thì xét theo LRU;<br /> LRU-Threshold [Abrams et al. 1995]: Tương tự như LRU, nhưng đối tượng có kích<br /> 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<br /> theo lịch sử tham chiếu và kích thước ngưỡng và tần số tham chiếu.<br /> GDS (GreedyDual-Size) [Cao and Irani, 1997]: Là mở rộng của SIZE, nó liên kết kích<br /> 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ó<br /> 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<br /> trong gán giá trị khóa.<br /> 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<br /> Cache. Tuy vậy, GDFS không dự đoán các truy nhập tương lai.<br /> Các thuật toán dựa vào chi phí:<br /> SLRU (Size-Adjusted LRU): Chọn đối tượng có tỷ số của chi phí trên kích thước tốt<br /> nhất để loại bỏ.<br /> LRU-LSC [Hosseini-Khayat 1997]: Sử dụng danh sách LRU để xác định tính “tích<br /> 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<br /> 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<br /> sách nhỏ hơn tổng dung lượng của cache.<br /> Hierarchical GreedyDual (Hierarchical GD): Thực hiện thay thế đối tượng theo GDS<br /> nhưng theo phân lớp.<br /> LFU-Aging [Arlitt et al. 2000]: Với LFU thì các đối tượng đã rất phổ dụng trong<br /> một quãng thời gian nào đó có thể lưu trong cache ngay cả khi chúng không được truy<br /> 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<br /> đư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<br /> và sử dụng ngưỡng.<br /> 2. NỘI DUNG CẦN GIẢI QUYẾT<br /> Trong kiến trúc Web caching phân tầng (Hierarchical Web Caching) [10], chúng tôi lựa<br /> 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<br /> cache: Institution Caches (IC), Regional Caches (RC), Central Caches (CC), Origin<br /> Caches (OC) [11].<br /> 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<br /> 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<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2017 55<br />  Điều khiển – Cơ điện tử - Truyền thông<br /> các Origin Web Servers. Các hệ thống Cache Engine có thể cài đặt cho các IC, RC, CC, và<br /> 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<br /> tán theo từng tầng và giữa các tầng.<br /> Thời gian đáp ứng trung bình cho truy nhập HTTP trong một kiến trúc Web caching<br /> phân tầng của ISP đã được chúng tôi đề xuất trong [11]:<br /> E[ RWC ]  E[ R3H ]  ( Miss3 )( E[ R2 H ]  ( Miss2 )( E[ R1H ]  ( Miss1 )( E[ R0 H ]))) (1)<br /> E[ R3H ], E[ R2 H ], E[ R1H ], E[ R0 H ] - Thời gian đáp ứng truy nhập trung bình của các<br /> cấp cache tương ứng: IC, RC, CC, và OC<br /> Miss3 , Miss2 , Miss1 - Tỷ số trượt cache (cache miss) ở các cấp cache tương ứng: IC,<br /> RC, CC, và OC.<br /> 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<br /> 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<br /> ở các cấp RC, CC, và OC cũng tương tự. Cho rằng IC có n Proxy Caches (từ Proxy Cache<br /> 0 đến Proxy Cache n-1), trong đó Proxy Cache 0 ở gần yêu cầu HTTP nhất và Proxy<br /> 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<br /> HTTP ở IC là tìm ở cấp ngang hàng (từ Proxy Cache 0 đến Proxy Cache n-1). Chỉ khi<br /> 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<br /> và OC.<br /> <br /> No No No No No<br /> Object in Proxy Object in Proxy Object in Proxy Object in Proxy<br /> Cache 0 ? Cache 1 ? Cache n -2? Cache n-1 ?<br /> <br /> <br /> Yes Yes Yes Yes<br /> <br /> <br /> http requests<br /> No<br /> Proxy Cache 0 Proxy Cache No No<br /> Proxy Cache<br /> is full ? n-3 is full ? n-2 is full ?<br /> <br /> Yes Yes Yes<br /> <br /> Cache<br /> Cache Cache<br /> Replacement<br /> Replacement Replacement<br /> <br /> <br /> <br /> <br /> Send Object to<br /> Send Object to Send Object to<br /> Proxy Cache 0<br /> Proxy Cache n-3 Proxy Cache n-2<br /> <br /> <br /> <br /> <br /> To Proxy cache<br /> Send Object Yes n-3 is full ? Yes<br /> Object already No Object already No Yes No<br /> to Client Object already<br /> in Proxy Cache in Proxy Cache in Proxy Cache<br /> 0? n-3 ? n-2 ? To<br /> RC<br /> <br /> <br /> <br /> Hình 1. Tìm đối tượng (Web page) ở IC cho yêu cầu Client HTTP.<br /> Đặt tỷ số trúng cache HR (Hit Rate) là H và đáp ứng trung bình của từng Proxy Cache<br /> là R, thì đối với cấp cache IC có tương ứng các giá trị:<br /> H IC 0 , RIC 0 , H IC1 , RIC1 ,.., H ICn1 , RICn1 . Tương tự, đối với RC, CC:<br /> H RC0 , RRC0 , H RC1, RRC1,.., H RCm1, RRCm1 , HCC0 , RCC0 , HCC1, RCC1,..,HCCk1, RCCk1.<br /> Đố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<br /> 0, nên ta không xét OC trong các công thức dưới đây.<br /> Đáp ứng trung bình của từng cấp cache là:<br /> <br /> <br /> <br /> 56 N. X. Trường, H. K. Lâm, “Đề xuất thuật toán thay thế cache… cung cấp dịch vụ Internet.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> E[RIC ]  E[R3H ]  RIC0  (1 HIC0 )(RIC1  (1 HIC1)(RIC2  (1 HIC2 )(RIC3  ...))) (2)<br /> E[RRC]  E[R2H ]  RRC0  (1 HRC0 )(RRC1  (1 HRC1)(RRC2  (1 HRC2 )(RRC3  ...))) (3)<br /> E[RCC]  E[R1H ]  RCC0  (1 HCC0 )(RCC1  (1 HCC1)(RCC2  (1 HCC2 )(RCC3  ...))) (4)<br /> E[ROC]  E[R0H ]  ROC0  (1 HOC0 )(ROC1  (1 HOC1)(ROC2  (1 HOC2 )(ROC3  ...))) (5)<br /> Kết hợp các công thức (1), (2), (3), (4), và (5), nhận được:<br /> n 1 m 1 k 1<br /> Miss3   (1  H ICi ); Miss 2   (1  H RCi ); Miss1   (1  H CCi ). (6)<br /> i 0 i 0 i 0<br /> <br /> Số lượng Web cache (Proxy Cache) càng lớn, tỷ số trúng cache (HR) của từng Web<br /> 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<br /> 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,<br /> 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<br /> kiến trúc Internet Web Caching.<br /> 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.<br /> 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<br /> độ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<br /> 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<br /> 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<br /> 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.<br /> 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<br /> 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ế<br /> theo LRU hay LFU, nhưng sau đó, chúng lại có thể được sự bùng nổ số người tham chiếu<br /> đế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<br /> hệ thống Web cache khác, mà chưa chắc đã tồn tại.<br /> <br /> <br /> <br /> <br /> Hình 2. Tiến trình thực hiện thuật toán LRU-EXT.<br /> 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ệ<br /> thống Web cache một web cache cục bộ mở rộng LEWC (Local Extended Web Cache) để<br /> 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<br /> 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ẽ<br /> 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.<br /> 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<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2017 57<br />  Điều khiển – Cơ điện tử - Truyền thông<br /> 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,<br /> 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<br /> 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ó<br /> 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<br /> 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<br /> có thể khắc phục được lỗi của SIZE và LRU-MIN.<br /> 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<br /> đố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<br /> 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<br /> 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.<br /> 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<br /> Cache ở cấp IC: IC0 và IC1.<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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ế<br /> đượ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<br /> 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<br /> 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ế<br /> 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<br /> hai vùng lân cận để thay thế.<br /> 3. MÔ PHỎNG, TÍNH TOÁN<br /> Time 0 1 2 3 4 5 6 7 8 9 10<br /> Requested web Object to g c a b d j k a c d<br /> Cache Cache<br /> k d d d d d d d k k k d<br /> Objects<br /> Cache<br /> <br /> <br /> <br /> <br /> j c c c c c c c k k k<br /> i b b b b b b b b b b b<br /> h a a a a a a j j a a a<br /> g g g g g g g g g c c<br /> Miss (M)/Hit (H) M H H H H M M H H H<br /> Size compare j=a k=d+c j=a c=g<br /> Hit Rate (HR) 7/10<br /> g c a b d j k a c d<br /> Replacement results by<br /> LRU-SIZE-MIN-REST: g c a b d j k a c<br /> last access queue of Proxy<br /> g c a b b b k a<br /> Cache 0<br /> g c c g g b b<br /> <br /> <br /> g g<br /> <br /> <br /> <br /> <br /> Extended Cache Buffer: a a d d j<br /> <br /> store replaced Objects in d c j g<br /> Proxy Cache 0<br /> c j g k<br /> <br /> <br /> <br /> <br /> Hình 3. Minh họa thực hiện thuật toán LRU-EXT.<br /> <br /> <br /> <br /> 58 N. X. Trường, H. K. Lâm, “Đề xuất thuật toán thay thế cache… cung cấp dịch vụ Internet.”<br /> Nghiên cứu khoa học công nghệ<br /> 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<br /> 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<br /> > 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 ><br /> 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à<br /> 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,<br /> 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<br /> không có trong Proxy Cache 1 lân cận. Do đó, với LRU chỉ đạt được HR = 4/10. Để không<br /> 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<br /> 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<br /> tính cả những đối tượng Web bị thay thế nhưng lại được ghi vào LEWC và sau đó được<br /> chuyển trở lại Web cache cho đáp ứng yêu cầu HTTP.<br /> Tỷ số trúng cache của thuật toán LRU-EXT được tính theo công thức sau:<br /> HNinC  HNin LEWC  Number of hit objinwebcache   Number of hit objinLEWC <br /> HRLRU  EXT   (7)<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   (8)<br /> TN Totalnumber of requested obj<br /> <br /> 4. KẾT LUẬN<br /> Từ công thức (7) và (8) cho thấy rõ ràng HRLRU  EXT  HRLRU khi cùng có chung<br /> 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<br /> 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ế<br /> 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-<br /> 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<br /> 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.<br /> Để chứng minh thuật toán LRU-EXT có đạt hiệu năng cao khi có nhiều Web cache ở<br /> 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ô<br /> 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<br /> 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ô<br /> hình hàng đợi và mạng Petri thời gian ngẫu nhiên.<br /> TÀI LIỆU THAM KHẢO<br /> [1]. Pablo Rodriguez, Christian Spanner, Ernst W.Biersack: “Web Caching Architectures:<br /> Hierarchical and Distributed Caching”. http://workshop99.ircache.net (4th<br /> International WWW Caching Workshop), Institut EUROCOM, france, 1999.<br /> [2]. Mukesh Dawar, Charanjit Singh, “A Review on Web Caching Techniques”.<br /> International Journal of Advanced Research in Computer Science and Software<br /> Engineering. Volume 4, Issue 3, March 2014. ISSN: 2277 128X.<br /> [3]. Kapil Arora, Dhawaleswar Rao Ch, “Web Cache Page Replacement by Using LRU<br /> and LFU Algorithms with Hit Ratio: A Case Unification”. Kapil Arora et al, /<br /> (IJCSIT) International Journal of Computer Science and Information Technologies,<br /> Vol. 5 (3) , 2014, 3232 – 3235. ISSN:0975-9646.<br /> [4]. Pranay Nanda, Shamsher Singh, G.L. Saini, “A Review of Web Caching Techniques<br /> and Caching Algorithms for Effective and Improved Caching”. International Journal<br /> of Computer Applications (0975 – 8887). Volume 128 – No.10, October 2015.<br /> [5]. Dhawaleswar Rao.CH, “Study of the Web Caching algorithms for performance<br /> Improvement of the response speed”. Indian Journal of Computer Science and<br /> Engineering (IJCSE). ISSN : 0976-5166. Vol. 3 No. 2 Apr-May 2012.<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2017 59<br />  Điều khiển – Cơ điện tử - Truyền thông<br /> [6]. A. I. Vakali, “LRU-based algorithms for Web Cache Replacement”. K. Bauknecht, S.<br /> Kumar Madria, and G. Pernul (Eds.): EC-Web 2000, LNCS 1875, pp. 409−418,<br /> 2000. © Springer-Verlag Berlin Heidelberg 2000.<br /> [7]. Stefan Podlipnig and Laszlo Boszormenyi, “A Survey of Web Cache Replacement<br /> Strategies”. Institute of Information Technology, University Klagenfurt,<br /> Universitatsstrasse 65-67, A-9020 Klagenfurt, Austria, ACM Computing Surveys,<br /> Vol. 35, No. 4, December 2003, pp. 374–398.<br /> [8]. Vinit A. Kakde et al. “Survey of Effective Web Cache Algorithm”. International<br /> Journal of Science and Engineering Investigations. vol. 1, issue 2, March 2012. Paper<br /> ID: 10212-16.<br /> [9]. Arun Pasrija, “Survey on Improving the Performance of Web by Evaluation of Web<br /> Prefetching and Caching Algorithms”. International Journal of Advanced Research in<br /> Computer Engineering & Technology (IJARCET). Volume No. 2, Issue No. 6, June<br /> 2013. ISSN: 2278 – 1323.<br /> [10].Pablo Rodriguez, Christian Spanner, Ernst W.Biersack: “Web Caching Architectures:<br /> Hierarchical and Distributed Caching”. http://workshop99.ircache.net (4th<br /> International WWW Caching Workshop), Institut EUROCOM, france, 1999.<br /> [11]. Ho Khanh Lam, Nguyen Xuan Truong, “Performance Analysis of Hybrid Web<br /> Caching Architecture”, American Journal of Networks and Communications. Vol. 4,<br /> No. 3, 2015, pp. 37-43. doi: 10.11648/j.ajnc.20150403.13.<br /> [12]. Haohuan Fu, Pui-On Au, and Weijia Jia, “Performance Evaluations of Replacement<br /> Algorithms in Hierarchical Web Caching”. Q. Li, G. Wang, and L. Feng (Eds.): WAIM<br /> 2004, LNCS 3129, pp. 176–185, 2004. © Springer-Verlag Berlin Heidelberg 2004.<br /> [13].George Kingsley Zipf, “Relative frequency as a determinant of phonetic change”.<br /> eprinted from the Havard Studies in Classical Philiology, Volume XL, 1929.<br /> ABSTRACT<br /> PROPOSING A REPLACE CACHE ALGORITHM FOR INTERNET WEB CACHING<br /> STRUCTURE OF INTERNET SERVICE STATION<br /> Nowadays, development of Internet and high speed of mobile networks attract<br /> the a large number of users to access Internet though www service from personal<br /> computers (PCs) and mobile devices such as smart phone. Some Internet structures<br /> such as web caching [1], web caching techniques [2] and replace web cache policis<br /> are good solution to provide for the requirement of Internet users. Since the 1990s<br /> of the last century has been researched and developed many the replace web cache<br /> algorithms. Based on the least recently used (LRU) algorithm, a policy replace for<br /> the content of web cache with named LRU-EXT and evaluate the performance of<br /> this policy is proposed in this paper.<br /> LRU-EXT saves the web contents in a extend cache memory of device network,<br /> which was moved out of web cache by LRU algorithm. These contents will be gotten<br /> from themselves instead of searching in other devices of same network layer or<br /> higher network layer. Therefore, it can reduce the time response of web to the user.<br /> Keywords: Web cache, Internet web caching, Cache replacement algorithms.<br /> <br /> Nhận bài ngày 02 tháng 5 năm 2017<br /> Hoàn thiện ngày 10 tháng 6 năm 2017<br /> Chấp nhận đăng ngày 20 tháng 7 năm 2017<br /> Địa chỉ: Trường Đại học Sư phạm Kỹ thuật Hưng Yên<br /> *<br /> Email: truongutehy@gmail.com<br /> <br /> <br /> <br /> 60 N. X. Trường, H. K. Lâm, “Đề xuất thuật toán thay thế cache… cung cấp dịch vụ Internet.”<br />