Đề 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 - Nguyễn Xuân Trường

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