Tài liệu Nghiên cứu một số thuật toán cho web caching và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Nguyễn Quang Thành NGHIÊN CỨU MỘT SỐ THUẬT TOÁN CHO WEB CACHING VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 60. 48. 01. 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS Nguyễn Văn Tam Thái Nguyên, năm 2016 i LỜI CAM ĐOAN Luận văn là kết quả nghiên cứu và tổng hợp các kiến thức mà học viên đã thu thập được trong quá trình học tập tại trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên, dưới sự hướng dẫn, giúp đỡ của các thầy cô và bạn bè đồng nghiệp, đặc biệt là sự hướng dẫn, giúp đỡ của PGS.TS Nguyễn Văn Tam. Tôi xin cam đoan luận văn không phải là sản phẩm sao chép của bất kỳ tài liệu khoa học nào. Học viên NGUYỄN QUANG THÀNH ii LỜI CẢM ƠN Đầu tiên tôi xin gửi lời cảm ơn sâu sắc nhất tới PGS.TS Nguyễn Văn Tam, người hướng dẫn khoa học, đã tận tình chỉ bảo, giúp đỡ tôi thực hiện luận văn. Tôi xin cảm ơn các thầy cô trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên đã giảng dạy và truyền đạt kiến thức cho tôi. Cuối cùng, tôi xin cảm ơn những người thân và các bạn bè chia sẻ, gúp đỡ tôi hoàn thành luận văn này. Mặc dù đã hết sức cố gắng hoàn thành luận văn với tất cả sự nỗ lực của bản thân, nhưng luận văn vẫn còn những thiếu sót. Kính mong nhận được những ý kiến đóng góp của quý Thầy, Cô và bạn bè đồng nghiệp. Tôi xin chân thành cảm ơn! Việt trì ngày 10 tháng 05 năm 2016 Nguyễn Quang Thành iii MỤC LỤC TRANG PHỤ BÌA LỜI CAM ĐOAN ........................................................................................... i LỜI CẢM ƠN ................................................................................................ ii MỤC LỤC .................................................................................................... iii PHỤ LỤCDANH MỤC CÁC KÍ HIỆU, CÁC CHỮ VIẾT TẮT .................. iv DANH MỤC CÁC KÍ HIỆU, CÁC CHỮ VIẾT TẮT .................................... v DANH MỤC CÁC HÌNH VẼ ...................................................................... vi DANH MỤC CÁC BẢNG ........................................................................... vii MỞ ĐẦU ....................................................................................................... 1 CHƯƠNG 1: TỔNG QUAN VỀ WEB CACHING........................................ 3 1.1. Giới thiệu web caching ........................................................................ 3 1.1.1. Vấn đề tải truy cập Internet và web caching ................................. 3 1.1.2. Định nghĩa web Caching .............................................................. 5 1.1.3. Một số khái niệm về Caching....................................................... 6 1.2. Các kiến trúc web Caching ................................................................. 9 1.2.1. Kiến trúc cache phân tầng và phân tán ......................................... 9 1.2.2. Kiến trúc kết hợp (Caching lai) .................................................. 14 1.3. Ưu nhược điểm của Web caching ...................................................... 18 1.4. Kết luận chương 1 ............................................................................. 19 CHƯƠNG 2: MỘT SỐ THUẬT TOÁN WEB CACHING .......................... 20 2.1. Thuật toán Least Frequently Used with Dynamic Aging (LFU-DA) . 20 2.2. Thuật toán Greedy Dual Size (GDS).................................................. 21 2.3. Thuật toán Cost Effective (CE) ......................................................... 21 2.4. Thuật toán Least recently used (LRU) ............................................... 23 2.4.1. Thay thế trang ............................................................................. 23 2.4.2. Các thuật toán thay thế trang....................................................... 24 2.4.3. Vấn đề thay thế Cache ................................................................ 28 2.5. Các thuật toán dựa trên LRU trong Web caching .............................. 32 2.6. Kết luận chương 2 ............................................................................. 38 CHƯƠNG 3: KỸ THUẬT CACHE TRONG WEB PROXY ....................... 39 3.1. Cơ bản về cache trong Squid ............................................................ 39 3.1.1. Lệnh cache_dir .......................................................................... 40 3.1.2. Thuật toán thay thế .................................................................... 43 3.1.3. Loại bỏ đối tượng Cache ............................................................ 45 3.2. Điều khiển cache trong Squid ........................................................... 49 3.2.1. Thông tin kết nối......................................................................... 50 3.2.2. Thông tin Cache.......................................................................... 52 3.2.3. Thời gian dịch vụ trung bình ....................................................... 53 3.2.4. Sử dụng tài nguyên ..................................................................... 55 iv 3.2.5. Hàm quản lý bộ nhớ sử dụng ...................................................... 57 3.2.6. Kỹ thuật quản lý bộ nhớ trong .................................................... 58 3.2.7. Mô tả các file sử dụng trong Squid ............................................. 58 3.2.8. Cấu trúc dữ liệu trong Squid: ...................................................... 60 3.3. Mô hình thử nghiệm và đánh giá kết quả .......................................... 61 3.3.1. Cài đặt Squid ............................................................................. 61 3.3.2. Thống kê, vẽ đồ thị ..................................................................... 67 3.3.3. Đánh giá kết quả ......................................................................... 71 3.4. Kết luận chương 3 ............................................................................. 71 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .................................................... 72 TÀI LIỆU THAM KHẢO ............................................................................ 73 PHỤ LỤC v DANH MỤC CÁC KÍ HIỆU, CÁC CHỮ VIẾT TẮT Kí hiệu Tên đầy đủ ISP Internet Service Provider ARPANET Advanced Research Projects Agency Network NSFNET National Science Foundation Network WAN Wide Area Network CPU Central Processing Unit LRU Least recently used LFU - DA Least Frequently Used with Dynamic Aging HLRU History LRU GDS Greedy Dual Size CE Cost Effective DNS Domain Name System WWW World Wide Web vi DANH MỤC CÁC HÌNH VẼ Hình 1.1. Vị trí của bộ nhớ Web cache ........................................................... 7 Hình 1.2. Sơ đồ biểu diễn Proxy server cache ................................................ 8 Hình 1.3. Vị trí đặt origin server cache .......................................................... 8 Hình 1.4. Mô hình phân cấp của ISP ............................................................. 9 Hình 1.5. Mô hình phân cây ......................................................................... 10 Hình 1.6. Sơ đồ đầy đủ một kiến trúc phân tầng Web Caching của một ISP . 11 Hình 1.7. Sơ đồ kiến trúc phân tán Web caching của một ISP ...................... 11 Hình 1.8. Sơ đồ Hybrid Web Caching của một ISP ...................................... 14 Hình 1.9. Thời gian kết nối trung bình cho toàn bộ N trang Web, phụ thuộc vào số cache kết hợp k.................................................................................. 15 Hình 1.10. Thời gian kết nối của Caching phân cấp, caching phấn tán và caching hỗn hợp ........................................................................................... 15 Hình 1.11. Thời gian truyền của N trang Web ............................................. 16 Hình 1.12. Thời gian truyền cho caching lai với số bộ đệm tối ưu k, ρ=0,8 . 17 Hình 2.1. Cấu trúc một phần tử trong bảng trang .......................................... 24 Hình 2.2. Lược đồ thay thế nội dung cache của thuật toán LRU .................. 25 Hình 2.3. Cấu trúc một phần tử trong bảng trang .......................................... 27 Hình 2.4. Thuật toán thay thế cache LRU ..................................................... 32 Hình 2.5. Thuật toán thay thế cache HLRU .................................................. 36 Hình 3.1. Mô hình thử nghiệm ..................................................................... 61 Hình 3.2. Giải nén thư mục nguồn................................................................ 62 Hình 3.3. Biên dịch # ./configure................................................................. 62 Hình 3.4. Bảy đường dẫn đặt Squid ............................................................. 63 Hình 3.5. Biên dịch mã nguồn ..................................................................... 64 Hình 3.6. Cài đặt Squid ................................................................................ 64 Hình 3.7. Giao diện chạy Squid ................................................................... 66 Hình 3.8. Giao diện chạy Squidclient .......................................................... 67 Hình 3.10. Cache hit và Byte hit, cùng số yêu cầu ........................................ 71 vii DANH MỤC CÁC BẢNG Bảng 2.1. Các thuộc tính hữu ích nhất của mỗi đối tượng lưu trữ i .............. 28 Bảng 2.2. Cấu trúc dữ liệu chính của LRU và HLRU ................................... 37 1 MỞ ĐẦU I. LÝ DO CHỌN ĐỀ TÀI Ngày nay, World Wide Web (WWW) ngày càng phát triển đi sâu vào mọi ngõ ngách cuộc sống hiện đại, là phương tiện truy cập mạng đơn giản, thân thiện với người sử dụng. Việc sử dụng dịch vụ Web đang tăng theo cấp số mũ, lưu lượng WWW trên các mạng Internet quốc gia và quốc tế cũng tăng đột biến. Và Việt Nam cũng không nằm ngoài vòng xoáy của cơn lốc WWW, cổng giao tiếp điện tử,....... đang là những ứng dụng mới và đang được phát triển. Trong tương lai, các ứng dụng này càng phát triển hơn cùng sự phát triển của hạ tầng mạng máy tính và đòi hỏi nền tảng công nghệ thông tin ngày càng cao. Tuy nhiên để có được điều đó không phải là vấn đề đơn giản. Hiện tại mạng máy tính tại Việt Nam ngày càng phát triển, tuy nhiên với điều kiện của nước ta, cơ sở vật chất hạ tầng mạng máy tính còn thấp kém. Chất lượng dịch vụ và thời gian đáp ứng có thể được cải thiện bằng cách giảm tải cho mạng, một trong số đó là phương pháp sử dụng kỹ thuật Webcaching. Kỹ thuật Web caching ra đời nâng cao được hiệu quả trong việc thực hiên tăng tốc các ứng dụng WWW. Bản thân làm công việc quản lý hệ thống mạng với mong muốn nghiên cứu về hạ tầng mạng cơ sở, tôi lựa chọn đề tài: “Nghiên cứu một số thuật toán cho Web Caching và ứng dụng”. Luận văn trước tiên nghiên cứu một số thuật toán Web Caching. Trên cơ sở đó, luận văn nghiên cứu và trình bày thuật toán LRU trong phần mềm Squid proxy để nâng cao hiệu quả ứng dụng WWW của hệ thống. Cuối cùng là chương trình thử nghiệm và đánh giá kết quả của thuật toán LRU trong Squid proxy tại ngân hàng Vietinbank chi nhánh đền Hùng - tỉnh Phú Thọ. II. MỤC TIÊU, ĐỐI TƯỢNG, PHẠM VI NGHIÊN CỨU  Mục tiêu Nắm bắt cơ bản được các thuật toán Web Caching và các ứng dụng của phương pháp này. 2 Trên cơ sở nghiên cứu, tìm hiểu lý thuyết về thuật toán LRU và thử nghiệm Web caching sử dụng thuật toán LRU.  Đối tượng và phạm vi nghiên cứu - Tìm hiểu xây dựng thuật toán LRU trong việc thử nghiêm Web Caching. - Cài đặt thử nghiệm. III. PHƯƠNG PHÁP NGHIÊN CỨU - Phương pháp nghiên cứu tài liệu, phân tích, tổng hợp. - Phương pháp trao đổi khoa học, lấy ý kiến chuyên gia. - Phương pháp thực nghiệm và đối chứng qua chương trình thử nghiệm. 3 CHƯƠNG 1: TỔNG QUAN VỀ WEB CACHING 1.1. Giới thiệu web caching 1.1.1. Vấn đề tải truy cập Internet và web caching 1.1.1.1. Vấn đề tải truy cập Internet Tiền thân của mạng Internet ngày nay là mạng ARPANET. Thuật ngữ "Internet" xuất hiện lần đầu vào khoảng năm 1974. Lúc đó mạng vẫn được gọi là ARPANET. Năm 1984, ARPANET được chia ra thành hai phần: ARPANET và MILNET. Đến năm 1980, ARPANET được đánh giá là mạng trụ cột của Internet. Giữa thập niên 1980 thành lập mạng liên kết các trung tâm máy tính lớn với nhau gọi là NSFNET. Sự hình thành mạng xương sống của NSFNET và những mạng vùng khác đã tạo ra một môi trường thuận lợi cho sự phát triển của Internet. Tới năm 1995, NSFNET thu lại thành một mạng nghiên cứu còn Internet thì vẫn tiếp tục phát triển. Các dịch vụ trên Internet không ngừng phát triển tạo ra cho nhân loại một thời kỳ mới: thời kỳ thương mại điện tử trên Internet. Việt Nam là nước có tốc độ tăng trưởng số người dùng internet trong tốp 10 nước có tốc độ tăng trưởng số người dùng nhanh nhất khu vực châu Á và cũng là một trong những nước có tốc độ tăng trưởng lớn so với thế giới (giai đoạn 2000-2009), tăng 10,662.2 %. Xu hướng tăng trưởng Internet Việt Nam Tính từ năm 2003, trung tâm INTERNET Việt Nam (VNNIC) thuộc Bộ thông tin và truyền thông, đã nghiên cứu và thống kê số liệu phát triển Internet tại Việt Nam theo bảng dưới đây. [8] Bảng 1.1. Thống kê số liệu phát triển Internet tại Việt Nam tính đến 2014 Tháng 05 năm Số người dùng % dân số sử dụng Số tên miền .vn đã đăng ký 2003 1.709.478 2,14 2.746 4 2004 4.311.336 5,29 7.088 2005 7.184.875 8,71 10.829 2006 12.911.637 15,53 18.530 2007 16.176.973 19,46 42.470 2008 19.774.809 23,50 74.625 2009 21.430.463 24,87 105.326 2010 23.068.441 26,89 136.953 2011 27.194.870 31,50 187.675 2012 30.645.089 35,11 265.567 - 396.817 - 493.311 Băng thông rộng: 4.761.543 2013 Thuê bao 3G: 3.433.530 2014 - 1.1.1.2. Những giải pháp tăng hiệu suất của INTERNET Tăng dung lượng truyền dẫn: Tăng dung lượng truyền dẫn là việc đầu tư, nâng cấp dung lượng truyền dẫn. Việc này sẽ triển khai đơn giản, nhanh nếu có sẵn các hệ thống truyền dẫn tuy nhiên nó sẽ trở nên phức tạp nếu hệ thống truyền dẫn không có sẵn. Ngoài ra chi phí thuê kênh quốc tế cũng rất đắt, việc vận hành khai thác các kênh truyền dẫn quốc tế cũng không đơn giản. Sử dụng thiết bị quản lý băng thông: Sử dụng thiết bị để ấn định mức độ băng thông cụ thể cho từng loại hình dịch vụ. Việc sử dụng thiết bị quản lý băng thông này có thể ấn định được mức độ băng thông cụ thể cho từng loại dịch vụ tuy nhiên chi phí đầu tư hệ thống cũng không nhỏ. Bên cạnh đó nếu băng thông không đủ lớn thì sẽ có 5 những dịch vụ bị ảnh hưởng đến chất lượng do bị lấy băng thông để dành cho dịch vụ ưu tiên, như vậy không thỏa mãn được tối đa nhu cầu người sử dụng. Sử dụng các hệ thống Web Caching: Ngày nay, World Wide Web (WWW) ngày càng phát triển đi sâu vào mọi ngõ ngách cuộc sống hiện đại, nhu cầu của người sử dụng ngày càng đòi hỏi nhiều hơn các về chất lượng dịch vụ mà nó cung cấp để chạy nhiều loại hình ứng dụng khác nhau. Bộ nhớ đệm Web caching là một giải pháp giảm thiểu các dịch vụ và tải giao thông mạng nút cổ chai, cải thiện thời gian đáp ứng yêu cầu và cải thiện các đối tượng Web có sẵn bằng cách lưu trữ một bản sao cache lưu trữ những đối tượng có thể sẽ sử dụng tới trong tương lai. Trong những năm gần đây, nhiều nghiên cứu đã được dành riêng để nâng cao hơn nữa hiệu suất của Web và cung cấp nhiều dịch vụ khác nhau cho người sử dụng. Tuy nhiên, nhiều việc cần phải được thực hiện khi cung cấp nhiều cấp độ dịch vụ trong proxy cache, nó đóng một vai trò quan trọng trong việc đẩy nhanh hiệu suất Web. Khi sử dụng giải pháp này, chúng ta sẽ tiết kiệm được băng thông WAN do việc đưa thông tin về gần với người sử dụng. Đảm bảo và nâng cao chất lượng truy nhập vì thời gian đáp ứng dịch vụ nhanh. Tuy nhiên nếu hệ thống không đủ lớn cũng có thể gây đến việc thường xuyên bị quá tải, có thể ảnh hưởng tới hoạt động của dịch vụ. Do đặc thù riêng của từng ISP mà mỗi ISP có cách lựa chọn giải pháp nâng cao chất lượng mạng riêng của mình. Và Web caching là một trong những giải pháp như vậy . 1.1.2. Định nghĩa web Caching Web caching (bộ nhớ đệm WEB) 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, cả về mặt chức năng trong web client hoặc những máy chủ bộ đệm lưu trữ riêng biệt. Cache (bộ đệm) được chia thành các loại: Browser cache (bộ đệm trình duyệt), Proxy Cache (bộ đệm ủy nhiệm), Gateway cache (bộ đệm cổng vào). [1] Cơ chế hoạt động WebCaching sử dụng một bộ nguyên tắc để xác định thời điểm cung cấp các đối tượng (hay các tài liệu Web), tất nhiên là với điều 6 kiện các đối tượng đó đã được lưu trong cache. Trường hợp các đối tượng được yêu cầu chưa được lưu sẵn trong cache thì cache server sẽ gửi các yêu cầu đó đến sever gốc. Một số nguyên tắc được thiết lập trong các giao thức HTTP/1.0, HTTP/1.1 và một số khác được thiết lập bởi những người quản trị cache: + Nếu phần tiêu đề của đối tượng cho cache biết không phải lưu đối tượng thì cache không lưu đối tượng đó. Nếu biến logic xác nhận ( biến validator) không xuất hiện, phần lớn các cache sẽ đánh dấu đối tượng là không thể lưu (uncacheable). + Nếu đối tượng có yêu cầu nhận thực hay bảo mật, nó sẽ được lưu. + Một đối tượng được lưu được coi là tươi – “fresh” có nghĩa là có thể được gửi tới client mà không cần sự kiểm tra của server gốc - Nó có thời gian tồn tại (hoạt động theo dạng một loại bộ đếm) còn nằm trong khoảng thời gian fresh (chưa quá hạn) - Nếu một browser cache đã từng hiển thị đối tượng và đối tượng này đã được đánh dấu là đã kiểm tra trong một phiên trước đó - Nếu proxy cache mới xử lý nó gần đây và nó đã được sửa đổi trước đó tương đối lâu, các đối tượng fresh được lấy trực tiếp từ cache mà không cần kiểm tra với server gốc + Nếu một đối tượng được coi là cũ, server gốc sẽ được yêu cầu xác nhận đối tượng hoặc báo cho cache rằng đối tượng đó vẫn còn giá trị sử dụng 1.1.3. Một số khái niệm về Caching Web caching giữ lại một bản sao của các trang web ở những nơi gần với người dùng cuối. Bộ đệm Caches được tìm thấy trong các trình duyệt và trong bất kỳ web trung gian giữa đại lý người dùng và máy chủ gốc. Thông thường, một bộ đệm cache nằm ở client (trình duyệt cache), máy chủ proxy (proxy cache) và máy chủ gốc (máy chủ cache) như thể hiện trong hình sau. [7] 7 Hình 1.1. Vị trí của bộ nhớ Web cache Browser cache Browser cache nằm trong các client. Browser cache hay còn được gọi là bộ đệm trình duyệt. Những trình duyệt như IE, Moziila, Firefox... chúng ta dùng để truy cập mạng, đều có sẵn một thư mục trong đó các nội dung đã được tải về sẽ được lưu để sử dụng trong tương lại. Bộ nhớ cache này rất hữu ích, đặc biệt là khi người sử dụng nhấn vào nút "back" hoặc bấm vào một liên kết để xem một trang mà họ đã xem qua. Ngoài ra, nếu người dùng sử dụng các hình ảnh chuyển hướng như nhau trong cả trình duyệt, họ sẽ được phục vụ từ cache trình duyệt gần như ngay lập tức. Proxy server cache Proxy server cache là máy chủ caching trung gian nhằm giảm tải lưu lượng trên đường truyền. Web Proxy Cache (bộ đệm Web Proxy) làm việc cùng nguyên tắc với Browser Cache nhưng ở quy mô lớn hơn. Nó được tìm thấy trong các máy chủ proxy giữa các máy client và máy chủ gốc. Nó hoạt động trên nguyên tắc tương tự của trình duyệt bộ nhớ cache, nhưng nó có một quy mô lớn hơn nhiều. Không giống như các cache của trình duyệt chỉ có một người sử dụng duy nhất, các proxy phục vụ hàng trăm hoặc hàng ngàn người sử dụng theo cùng một cách. Khi nhận được yêu cầu, các proxy server sẽ kiểm tra bộ nhớ cache của nó. Nếu đối tượng có sẵn, nó sẽ gửi các đối tượng cho khách hàng. Nếu đối tượng là không có, hoặc đã hết hạn, các máy chủ proxy sẽ yêu cầu các đối tượng từ máy chủ gốc và gửi nó cho khách hàng. 8 Các đối tượng sẽ được lưu trữ trong bộ nhớ cache của địa phương đại diện cho các yêu cầu trong tương lai. Hình 1.2. Sơ đồ biểu diễn Proxy server cache Origin server cache Ngay cả tại các máy chủ gốc, các trang web có thể được lưu trữ trong một bộ nhớ cache phía máy chủ để giảm sự cần thiết cho các tính toán dự phòng hoặc cơ sở dữ liệu có khả năng tìm lại. Do đó, việc tải server có thể được giảm bớt nếu bộ nhớ cache máy chủ gốc cũng làm việc. Origin server cache (Gốc máy chủ cache) là máy chủ caching nằm trước các Web server (máy chủ web) nhằm giảm tải cho các web server. Nó thường được biết đến như là “reverse proxy cache”. Hình 1.3. Vị trí đặt origin server cache 9 Các bộ nhớ đệm proxy được sử dụng rộng rãi bởi các quản trị mạng máy tính, các nhà cung cấp công nghệ, và các doanh nghiệp để giảm sự chậm trễ sử dụng và để giảm bớt tắc nghẽn Internet. 1.2. Các kiến trúc web Caching 1.2.1. Kiến trúc cache phân tầng và phân tán Kiến trúc phân tầng: mỗi một thành phần của mạng được xem như một hệ thống gồm nhiều tầng, và mỗi một tầng bao gồm nhiều chức năng truyền thông. Các tầng được chồng lên nhau, số lượng và chức năng phụ thuộc vào các nhà sản xuất và thiết kế. Tuy nhiên quan điểm chung là trong mỗi tầng có nhiều thực thể ( các tiến trình) thực hiện một số chức năng nhằm cung cấp một số dịch vụ, thủ tục cho các thực thể tầng trên hoạt động. Kiến trúc phân tán là tổ hợp bao gồm cá máy tính độc lập với trình diễn hệ thống như một máy tính đơn trước người dùng. Do đó có các đặc điểm cơ bản là: tính chia sẻ tài nguyên, tính mở, khả năng song song, tính mở rộng, khả năng thứ lỗi, tính trong suốt. Kiến trúc phân tầng có thời gian kết nối nhỏ hơn kiến trúc phân tán. Bởi vì trong kiến trúc phân tầng các bản sao của một trang được lưu trữ một cách dư thừa tại các hệ thống cache ở các cấp độ mạng khác nhau dẫn tới giảm được thời gian kết nối. Ngược lại kiến trúc phân tán có thời gian truyền nội dung của trang Web thấp hơn kiến trúc phân tầng, bởi vì trong kiến trúc phân tán lưu lượng Web được lưu chuyển trên các tầng mạng phía dưới và ít bị nghẽn hơn. Mô hình mạng Hình 1.4. Mô hình phân cấp của ISP 10 Chúng ta xây dựng topology của mạng dưới dạng cấu trúc cây đầy đủ Oary, hình dưới đây: Hình 1.5. Mô hình phân cây trong đó: - O đại diện cho độ mở (số nhánh) của mỗi nút trong cấu trúc cây - H là số đường kết nối mạng giữa nút gốc của mạng quốc gia với nút gốc của mạng cấp vùng. H cũng đại diện cho số đường kết nối giữa nút gốc của mạng cấp vùng với nút gốc của mạng cấp khu vực. - z là số kết nối giữa máy chủ gốc và nút gốc - l là số cấp của cây (0≤ 1≤ 2H+z) trong đó:  l = 0 là mức mạng của các bộ đệm cơ quan  l = H là mức mạng của các bộ đệm vùng  l = 2H là mức mạng của các bộ đệm quốc gia  l = 2H + z máy chủ gốc Giả định băng thông là đồng nhất với mỗi ISP (mỗi kết nối giữa các ISP có cùng tốc độ truyền dẫn (transmission rate)). - CI, CR, CN là tốc độ truyền dẫn (transmission rate) của các kết nối ở mạng cơ quan, vùng, quốc gia. - C: tỷ lệ nghẽn nút cổ chai trên đường truyền dẫn quốc tế Kiến trúc phân tầng 11 Hình 1.6. Sơ đồ đầy đủ một kiến trúc phân tầng Web Caching của một ISP Hệ thống cache thường được đặt tại điểm truy nhập giữa hai mạng khác nhau để giảm chi phí truyền trang qua một mạng mới. Tại một nước thì chỉ có một mạng quốc gia và một hệ thống cache quốc gia. Vậy sẽ có OH mạng vùng và mỗi mạng sẽ có một hệ thống cache cấp vùng. Có O2H mạng khu vực và mỗi mạng sẽ có một hệ thống cache cấp khu vực. Hệ thống cache được đặt ở độ cao 0 của cấu trúc cây tương ứng cấp độ 1 trong kiến trúc phân tầng, độ cao H của cấu trúc cây tương ứng cấp độ 2 trong kiến trúc phân tầng, độ cao 2H của cấu trúc cây tương ứng cấp độ 3 trong kiến trúc phân tầng. Cache được nối tới các ISP qua các kênh truy nhập. Chúng ta giả sử rằng dung lượng kênh truy nhập tại mỗi cấp độ bằng dung lượng kênh trung kế của mạng tại cấp độ đó nghĩa là CI, CR, CN và C cho từng cấp độ tương ứng. Tỷ lệ hit tại hệ thống cache của các cấp khu vực, vùng, quốc gia được đại diện bởi các giá trị: hitI, hitR, hitN (hit: số phần trăm yêu cầu được đáp ứng ở mức bộ đệm). Kiến trúc phân tán Hình 1.7. Sơ đồ kiến trúc phân tán Web caching của một ISP 12 Cache chỉ được đặt tại cấp khu vực và sẽ không có bản sao trung gian của các trang Web tại các cấp mạng khác. Để chia sẻ các bản sao giữa các hệ thống cache khu vực, hệ thống cache tại cấp mạng trung gian sẽ lưu giữ dữ liệu meta-data nó chứa đựng thông tin về nội dung được lưu trong các hệ thống cache khu vực. Các cache khu vực trao đổi định kỳ lượng thông tin meta-data về các tài liệu mà chúng lưu trữ. Chúng ta giả sử rằng các thông tin là thường xuyên cập nhật tại tất cả các cache khu vực khi mà có một tài liệu mới được lấy về ở bất kỳ cache nào. 1.2.1.1. Thời gian kết nối Tc Thời gian kết nối là phần đầu tiên của độ trễ khi truy vấn lấy văn bản (nội dung). Chúng ta giả sử thời gian kết nối chỉ phụ thuộc vào khoảng cách từ client đến với văn bản xét trên phạm vi mạng lưới. Thời gian kết nối đến một văn bản có độ phổ biến tot đối với trường hợp sử dụng caching phân tán và caching phân cấp. Khoảng thời gian cập nhật trong trường hợp này = 24 giờ; thời gian cập nhật càng dài thì số lượng các yêu cầu càng tăng. Tuy nhiên hiệu năng tương đối của mô hình caching phân tán và caching phân cấp vẫn tương đương nhau. Trước hết, với một văn bản không phổ biến (tot nhỏ), cả hai mô hình phân tán và phân cấp đều có thời gian kết nối khá cao do yêu cầu kết nối phải chuyển tới máy chủ chứa văn bản đó. Khi một văn bản hay được truy cập, thời gian kết nối của mô hình phân tán và mô hình phân cấp là rất gần nhau do xác suất văn bản được tìm thấy ở máy chủ caching ở biên mạng cao. 1.2.1.2. Thời gian truyền Tt Phân bố của lưu lượng được tạo ra bởi mô hình caching phân tán βdl và mô hình caching phân cấp βhl ở tất cả các cấp độ mạng. Với N=250 triệu trang Web, phân bố theo luật Zipf. Thời gian cập nhật một trang là =24h. Tổng lưu lượng mạng O2H.βI=1000 truy nhập/s. Chúng ta cố định kích thước trang S=15KB. Ta tính được tỷ lệ hit tại mỗi cấp độ cache hitI=0.5, hitR=0.6 và hitN=0.7 Mô hình caching phân tán gây tăng gấp 2 lần băng thông ở các mức mạng thấp và sử dụng nhiều băng thông hơn ở mức mạng quốc gia so với mô hình caching phân cấp. Tuy nhiên, lưu lượng ở những nút mạng bị nghẽn lại