Đá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

Số trang: 14 Loại file: pdf Dung lượng: 640.91 KB Lượt xem: 232 Lượt tải: 0

tailieu_vip

Phí lưu trữ: 1,000 VND

Xem trước 2 trang đầu tiên của tài liệu này:

Thông tin tài liệu:

Web caching là việc lưu trữ bản sao của những tài liệu web sao cho gần với người dùng; Web caching là ứng dụng ở cấp độ routing và phần lớn băng thông 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. Các kiến trúc Internet web caching cùng với các chính sách thay thế Web cache là những giải pháp quan trọng và không thể thiếu được trong phát triển Internet nhằm đáp ứng các dịch vụ chất lượng cao.
Nội dung trích xuất từ tài liệu:
Đá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 ĐÁNH GIÁ HIỆU NĂNG CỦA THUẬT TOÁN THAY THẾ WEB CACHE 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 Nguyễn Xuân Trường*, Hồ Khánh Lâm, Nguyễn Minh Quý 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 với người dùng; Web caching là ứng dụng ở cấp độ routing và phần lớn băng thông 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. Các kiến trúc Internet web caching cùng với các chính sách thay thế Web cache là những giải pháp quan trọng và không thể thiếu được trong phát triển Internet nhằm đá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, LFU, MRU… đã được ứng dụng từ lâu, tuy nhiên mỗi thuật toán đều có những ưu điểm và nhược điểm. Do đó, cho đến nay các nghiên cứu về thay thế Web cache vẫn còn được quan tâm. Thuật toán thay thế Web cache LRU-EXT đã được đề xuất [1] 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, 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 chung để đánh giá hiệu năng của thuật toán LRU-EXT. Từ khóa: Internet web caching architecture; LRU-EXT; Hybrid model of Queue and GSPN. 1. MỞ ĐẦU Trong kiến trúc Web caching phân tầng (Hierarchical Web Caching) [2], 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: Institutional Caches (IC), Regional Caches (RC), Central Caches (CC), Original Caches (OC) [3]. 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 [3]: E[ RWC ]  E[ R3 H ]  ( Miss3 )( E[ R2 H ]  ( Miss2 )( E[ R1H ]  ( Miss1 )( E[ R0 H ]))) (1) Trong đó: E[ R3 H ], E[ R2 H ], E[ R1H ], E[ R0 H ] - 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; Miss3 , Miss2 , Miss1 - Tỷ số trượt cache (cache miss) ở các cấp cache tương ứng: IC, RC, CC, và OC. Sự thay thế Web cache được thực hiện khi trượt Web cache, nghĩa là khi đối tượng mà yêu cầu http từ người dùng (client http request) không có trong Web cache mà dung lượng của Web cache đã đầy không còn vùng trống để nhận vào đối tượng 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 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 chung ở một cấp cache (ví dụ cấp IC) của kiến trúc Internet web caching được chúng tôi đề xuất trong [1] cho ở hình 1. Thuật toán LRU (Least Recently Used) 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, xét theo Zipf [4]: 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 để đáp ứng nhu cầu. Vậy 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.” Nghiên cứu khoa học công nghệ 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. Hình 1. Tìm đối tượng Web ở cấp cache IC cho yêu cầu Client HTTP. Do đó không áp dụng các thuật toán LRU hay LFU (Least Frequently Used) 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. Thực tế đã có đề xuất thuật toán MRU (Most Recently Used) đối tượng được sử dụng gần đây nhất là ứng viên bị thay thế [5]. 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 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 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 đ ...