Tài liệu Nghiên cứu giải pháp tối ưu hệ thống web caching

1 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ---------------------------------------- PHAN VŨ HẢI VÂN NGHIÊN CỨU CÁC GIẢI PHÁP TỐI ƯU HỆ THỐNG WEB CACHING Chuyên ngành: Truyền dữ liệu và Mạng máy tính Mã số: 60.48.15 Người hướng dẫn khoa học: TS. HỒ KHÁNH LÂM TÓM TẮT LUẬN VĂN THẠC SỸ HÀ NỘI – 2010 2 MỞ ĐẦU Hơn 80 phần trăm lưu lượng của Internet là các lượng truy nhập truyền thông với các nội dung web. Ngày nay, với sự phát triển của các công nghệ truyền thông băng rộng, công nghệ truyền thông đa phương tiện qua WWW càng phát triển mạnh mẽ. Sự cung cấp các dịch vụ thông tin về kinh tế, văn hoá, xã hội ngày càng phong phú trên mạng cũng như xu thế tích hợp các hệ thống thông tin trong các hoạt động chính trị, kinh tế, xã hội trên giao diện Web nói riêng, cũng như việc tối ưu hoá lưu lượng thông tin, hạn chế đến mức tối đa khả năng tắc nghẽn trên mạng trở nên rất cần thiết. Web trở thành một ứng dụng thành công bậc nhất trên Internet. Tuy nhiên sự nâng cấp cần thiết của các máy chủ và băng thông của mạng Internet không theo kịp sự phát triển với luật số mũ (luật Zipf) của nhu cầu khách hàng trong vài năm qua, do đó chất lượng các dịch vụ yêu cầu băng thông rộng và thời gian thực được truy nhập qua Web còn bị hạn chế, chưa đáp ứng nhu cầu càng cao của người sử dụng. Như vậy, ngoài những giải pháp tốn kém, như tăng băng thông của kênh truyền dẫn ở các cấp mạng, tăng công suất của các nút mạng truy nhập, mạng địa phương, mạng trục Internet, các nhà cung cấp dịch vụ Internet đưa vào kiến trúc Web caching. Đây là một cách để giảm độ trễ truy nhập các nội dung Web, và tiết kiệm băng thông của các kênh truyền dẫn giữa các tầng mạng của Internet. Cách này đảm bảo lưu trữ các bản sao cùng các nội dung Web trong các bộ nhớ đệm trên các hệ thống máy chủ phân tán trên các nút truy nhập ở các tầng mạng. Mục đích của luận văn này nhằm tìm hiểu thế nào là Web caching, các kiểu kiến trúc Web Caching, các thuật toán thay thế cache và hiệu năng của nó ra sao. Vận dụng những kiến thức đã nghiên cứu đó để đánh giá hệ thống Web Caching hiện tại dùng cho mạng VNN.VN của VNPT, đưa ra giải pháp Web Caching mới tối ưu hơn cho mạng VNN.VN. 3 Chương 1- NHỮNG ĐẶC ĐIỂM CỦA INTERNET 1.1. LỊCH SỬ VÀ TỐC ĐỘ PHÁT TRIỂN INTERNET 1.1.1. Lịch sử 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. 1.1.2. Tốc độ sử dụng Internet tại Việt Nam 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 %. 1.1.3. Xu hướng tăng trưởng Internet Việt Nam Bảng 1.2. Thống kê số liệu phát triển Internet tại Việt Nam tính đến 2009 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 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 1.2. NHỮNG GIẢI PHÁP TĂNG HIỆU SUẤT CỦA INTERNET 1.2.1. 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 4 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. 1.2.2. 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ó 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. 1.2.3 Sử dụng các hệ thống Web Caching: 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. Chương 2- KHÁI NIỆM WEB CACHING, CÁC KIẾN TRÚC VÀ THUẬT TOÁN THAY THẾ CỦA WEB CACHING 2.1. KHÁI NIỆM VỀ WEB CACHING 2.1.1. Định nghĩa Web Caching 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, 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). 2.1.2. Một số khái niệm Cache  2.1.2.1. Browser cache 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... bạn 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. 5  2.1.2.2. Proxy Cache Proxy 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. Hình 2.1. Sơ đồ biểu diễn Proxy cache  2.1.2.3. Gateway cache Gateway 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 2.2. Vị trí đặt gateway cache 2.2. CÁC LOẠI KIẾN TRÚC WEB CACHING 2.2.1. Caching phân tầng (Hierarchical cache) Hình 2.3. Sơ đồ đầy đủ một kiến trúc phân tầng Web Caching của một ISP 6 2.2.2. Caching phân tán (Distributed cache) Hình 2.4. Sơ đồ kiến trúc phân tán Web caching của một ISP 2.2.3. Caching kết hợp (Hybrid scheme) Hình 2.5. Sơ đồ Hybrid Web Caching của một ISP 2.3. CÁC THUẬT TOÁN CACHE 2.3.1.Thuật toán Least recently used (LRU) Thuật toán giả định là một trang vừa mới được lấy ra khỏi cache sẽ tiếp tục được truy nhập trong thời gian tới. Để thay thế một nội dung trong cache, LRU sẽ xoá bỏ các trang không được truy cập đến trong một khoảng thời gian dài nhất. Chức năng của LRU được minh hoạ trong hình dưới đây: Hình 2.6: Lược đồ thay thế nội dung cache của thuật toán LRU 7 LRU là thuật toán cache được sử dụng rộng rãi nhất, bởi vì LRU coi các trang có chi phí (cost) và kích thước không đổi, mục đích của LRU là tối ưu hoá tỷ lệ hit . Ưu điểm của LRU là khai thác được đặc tính cục bộ của truy nhập. Nhược điểm của LRU là bỏ qua sự thay đổi về chi phí và kích thước của trang, cũng như LRU không tính đến tần suất của các truy nhập. 2.3.2. Thuật toán Least Frequently Used with Dynamic Aging (LFU-DA) LFU-DA là thuật toán dựa trên tần suất truy nhập, trong đó giả định chi phí và kích thước của trang là không đổi. Trong thuật toán LFU, quyết định loại bỏ nội dung một trang căn cứ vào số lần truy nhập đến trang đó. Việc đếm số lần truy nhập của tất cả các trang trong cache được lưu lại và trang có số lần truy nhập đến nhỏ nhất sẽ bị loại bỏ. Thuật toán LFU-DA được mở rộng từ LFU bằng cách sử dụng thêm thuật toán tuổi động ( Dynamic Aging ). Qua thực nghiệm người ta quan sát được tỷ lệ byte hit ( là tỷ lệ giữa tổng kích thước trang Web được yêu cầu có nội dung nằm sẵn trong cache với tổng kích thước trang Web được yêu cầu) của thuật toán LFU-DA là khá cao. 2.2.3. Thuật toán Greedy Dual Size (GDS) Thuật toán này đã tính đến sự thay đổi của chi phí và kích thước của trang. Việc loại bỏ trang khỏi hệ thống được căn cứ trên tỷ lệ giữa kích thước và chi phí của trang.Cũng giống như thuật toán LFU-DA, GDS gán một giá trị H(p) với một trang p trong cache. Khi một trang mới được lưu vào trong cache hoặc khi một trang đang nằm trong cache được truy nhập lại thì giá trị H(p) được cập nhật lại: H(p)=C(p)/S(p). Trong đó S(p) là kích thước của trang, C(p) là hàm chi phí thể hiện chi phí để lưu một trang p vào trong cache. Trang p có giá trị H(p)=Hmin:=minpH(p) ( của tất cả các trang nằm trong cache) sẽ bị loại bỏ khỏi cache khi có yêu cầu thay thế trang. Tiếp theo đó L được đặt bằng giá trị H(p) của trang bị loại bỏ. Tuy nhiên cũng giống như LRU, GDS không tính đến tần suất truy nhập . 2.2.4 Thuật toán Cost Effective (CE) Thuật toán CE được đưa ra để giảm toàn bộ chi phí lấy được tài liệu. Nhìn chung, những người sử dụng Internet có thể được chia 2 nhóm như sau: (i)Khách hàng tìm kiếm thời gian đáp trả ngắn hơn (ii)Khách hàng tìm cách tối đa hóa sử dụng băng thông (ví dụ một Internet Service Provider, ISP). Vì vậy, có hai mô hình chi phí để tối ưu hóa proxy cache cho hai nhóm mục tiêu sử dụng. Thứ nhất, một mô hình độ trễ mà có thể đo độ trễ tải về của người dùng cuối, và thứ hai là một mô hình lưu lượng truy cập mà có thể đo được lưu lượng mạng. Chúng tôi xác định tỷ lệ giảm chi phí (CRR) như sau: 8 CRR   H i  Ci * 100% với Hi=1 nếu yêu cầu i là Hit còn lại là Hi=0  Ci Ci là chi phí lấy được đối tượng i Chúng tôi xác định chi phí như là độ trễ tải về quan sát được của người dùng trong mô hình độ trễ, và là số lưu lượng mạng được tạo ra trong mô hình lưu lượng. Trong CE, giá trị lợi ích (Benefit Value-BV) được gán cho mỗi đối tượng, biểu diễn tầm quan trọng của nó trong cache. Khi cache đầy, các đối tượng với BV thấp nhất bị thay thế. BV bao gồm 3 phần: chi phí, xác suất tái truy cập (Pr) và tuổi động. Xác suất tái truy cập BV=(Cost/Size)*Pr +Age Cost: Chi phí lấy được đối tượng từ máy chủ. Pr Xác suất tái truy cập: Pr  1/  Pf ( Log10 Size) b với Pf=Df+1/Df Pf là xác suất có điều kiện của việc tái truy cập 1 đối tượng đã được truy cập f lần Df Số tài liệu được truy cập ít nhất là f lần α Giá trị đặc trưng của luật phân bố Zipf b là hằng trọng số Size Kích thước của đối tượng được yêu cầu Age Tuổi của cache, được xác định là BV bé nhất của tất cả các đối tượng Nếu một đối tượng đã được đọc f lần , ước tính xác suất tái truy cập là Pf = Df+1 / Df , Df là số tài liệu được truy cập ít nhất f lần. Tỷ lệ truy cập trung bình của một đối tượng có thể được ước tính bởi kích thước của nó. Cho R là tỷ lệ truy cập trung bình cho một đối tượng và S là kích thước của nó. R có thể được ước tính là R = C / Sb, nơi C và b là hai hằng. Tỷ lệ truy cập trung bình : Ps  C b với b=1,3 và C là hằng ( Log 10 Size) Brelau giới thiệu một mô hình cho các yêu cầu trang web, theo luật Zipf: P K R 9 R là độ thông dụng của trang , K và α là 2 tham số độc lập Tuổi cache là thời gian truy cập gần đây nhất. Khi một đối tượng được đưa đến cache, BV của nó là chi phí lấy được đối tượng cộng với H (ban đầu H = 0). Trong trường hợp cache hit, H được đặt bằng thời gian hiện nay. Chương 3- PHÂN TÍCH HIỆU NĂNG CỦA CÁC KIẾN TRÚC WEB CACHING VÀ CÁC THUẬT TOÁN THAY THẾ 3.1.PHÂN TÍCH, SO SÁNH HIỆU NĂNG KIẾN TRÚC WEB CACHING 3.1.1 Kiến trúc cache phân tầng và phân tán 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 gia 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 3.1. Mô hình phân cấp của ISP Chúng ta xây dựng topology của mạng dưới dạng cấu trúc cây đầy đủ O-ary, hình dưới Hình 3.2. Mô hình phân cây 10  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 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 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 11 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. 3.1.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, chúng ta thấy rằng 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. 3.1.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 được giảm đi chỉ còn 1/2. Chúng ta thiết lập băng thông mạng ở cấp khu vực CI = 100Mb/s. Mạng ở cấp độ quốc gia và vùng có băng thông như nhau CN = CR. Chúng ta không cố định hai băng thông này mà chỉ xem xét độ nghẽn mạng ρ (    h 2 H .S ) của hai mạng này (chúng ta thay đổi mức độ sử dụng băng CN thông ρ của các kết nối mạng cấp quốc gia trong kiến trúc caching phân cấp). Kết nối quốc tế thường xuyên nghẽn và có mức độ sử dụng băng thông (β1O2H(1-hitN)S/C) = 0.95. Nút thắt cổ chai lưu lượng duy nhất trên đường kết nối từ client đến máy chủ gốc là đường kết nối quốc tế. Chúng ta quan sát thấy hiệu năng của mô hình phân tán và phân cấp khá giống 12 nhau vì không có kết nối bị nghẽn cao ở các mạng cấp vùng và cấp quốc gia. Mô hình caching phân tán có thời gian truyền dẫn thấp hơn phân cấp vì có nhiều yêu cầu được thỏa mãn ở các mức mạng không bị nghẽn. 3.1.1.3. Thời gian trễ tổng thể Thời gian trễ tổng thể là tổng thời gian kết nối và thời gian truyền dẫn. Với các văn bản lớn, thời gian trễ tổng thể sẽ xấp xỉ với thời gian truyền dẫn. Với các văn bản nhỏ, thời gian truyền dẫn rất nhỏ và trong trường hợp này, thời gian trễ tổng thể sẽ xấp xỉ với thời gian kết nối. Mô hình mạng phân tầng (phân cấp) có thời gian trễ thấp hơn với các văn bản nhỏ hơn 200KB do mô hình mạng caching phân cấp có thời gian kết nối thấp hơn mô hình caching phân tán. Tuy nhiên mô hình mạng caching phân tán có thời gian trễ thấp hơn trong trường hợp các văn bản có kích thước lớn do thời gian truyền dẫn của mô hình này nhỏ hơn. Mức ngưỡng của dung lượng văn bản phụ thuộc vào mức độ nghẽn của mạng quốc gia. Nghẽn càng lớn thì với mức ngưỡng kích thước văn bản càng nhỏ, mô hình caching phân tán có độ trễ nhỏ hơn mô hình caching phân cấp. 3.1.1.4. Băng thông sử dụng Tính toán lượng băng thông sử dụng dựa trên số lượng đường link (liên kết) cần thiết để gửi trả về 1 gói tin cho clients (khách hàng). Mô hình caching phân tán sử dụng nhiều băng thông hơn mô hình caching phân cấp trong mạng cấp. Tuy nhiên lưu lượng mạng được phân tán tốt hơn với phần lớn băng thông được sử dụng ở các mức mạng ít nghẽn. Ngoài ra các mô hình caching phân cấp sử dụng ít kết nối hơn trong mạng cấp vùng do các văn bản được tìm thấy ở máy chủ caching cấp vùng. Ở cấp mạng quốc gia cũng tương tự như vậy. Vì vậy các hướng tiếp cận chỉ sử dụng các chủ caching ở mức biên và máy trạm để cung cấp ứng dụng nội dung thường có hiệu năng kém xét về mặt băng thông hơn các hướng tiếp cận khác 3.1.2. Kiến trúc kết hợp (Caching lai) Kiến trúc cache lai là kiến trúc có một số lượng xác định k cache liên kết tại mọi mức mạng của kiến trúc phân tầng. 3.1.2.1. Thời gian kết nối Tc Thời gian kết nối trong kiến trúc kết hợp phụ thuộc vào số lượng cache kết hợp k tại mỗi cấp mạng. Số lượng cache kết hợp tại mỗi cấp thay đổi từ 1 tới OH = 64 (toàn bộ số lượng cache bên cạnh trong cùng một cấp độ cache kết hợp). Hình dưới cho ta thấy 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 13 Hình 3.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 Khả năng tìm thấy một trang tại hệ thống cache bên cạnh gần đấy là rất nhỏ, như vậy phần lớn yêu cầu được cache cấp trên phục vụ với một khoảng cách H hop. Khi số cache kết hợp tăng lên, thời gian kết nối giảm tới một giá trị nhỏ nhất. Bời vì khả năng để truy nhập được một trang tại hệt hống cache bên cạnh gần hơn so với hệ thống cache cấp trên.Tuy nhiên khi số cache kết hợp tăng quá ngưỡng kc=4, thì thời gian kết nối tăng rất nhanh bởi vì trang được yêu cầu từ hệ thống cache bên cạnh có khoảng cách mạng lớn. Số lượng cache kết hợp tối ưu kc để tối thiểu hóa thời gian kết nối là số lượng cache mà khoảng cách mạng gần hơn so với mạng cấp trên: kc=O[H/2] Chúng ta thấy là kiến trúc hỗn hợp với số kết nối tối ưu kc có thời gian kết nối nhỏ hơn kiến trúc phân tán và thậm chí nhỏ hơn kiến trúc phân tầng trong một khoảng lớn. Hình 3.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 3.1.2.2. Thời gian truyền Tt Hình 3.11 biểu diễn cho thời gian truyền của tất cả N trang Web phụ thuộc vào số cache kết hợp tại mỗi cấp. 14 Hình 3.11. Thời gian truyền của N trang Web Sau khi xem xét hai trường hợp mạng cấp quốc gia không nghẽn (ρ=3) điểm nút cổ chai là các đường quốc tế, và mạng cấp quốc gia nghẽn (ρ=0.8), chúng ta nhận thấy rằng khi mạng quốc gia không nghẽn thì sự thay đổi số lượng cache kết hợp không ảnh hưởng đến thời gian truyền. Tuy nhiên khi mạng quốc gia bị nghẽn thì thời gian truyền phụ thuộc nhiều vào số lượng cache kết hợp tại mỗi cấp mạng. Nếu số lượng cache kết hợp rất nhỏ, thì có ít khả năng trang Web được lấy từ cache bên cạnh. Các trang phần lớn được lấy từ cache cấp trên qua các đường kết nối ở mức trên cũng bị nghẽn nặng. Khi số cache kết hợp tăng, khả năng để nhận một trang tại hệ thống cache bên cạnh tăng và như vậy thời gian truyền nhỏ đi. Nếu số cache kết hợp vượt qua ngưỡng kt =16, thời gian truyền lại tăng lại bởi vì các trang Web sẽ được nhận qua các có khoảng cách lớn và các đường kết nối bị nghẽn nặng. Số cache kết hợp tối ưu kt để tối thiểu hóa thời gian truyền phụ thuộc vào số lượng cache kết hợp có thể đạt được mà không làm nghẽn các kênh kết nối. Trong trường hợp kênh ở lớp trên cùng của mạng cấp quốc gia bị nghẽn, số lượng cache kết hợp tối ưu tại mỗi cấp là kt =16. Giá trị này tương ứng với số cache vùng có thể kết hợp với nhau để đáp ứng yêu cầu truy nhập mà không cần phải đi đến các đường kết nối cấp quốc gia: kt=OH-1 Hình 3.12. Thời gian truyền cho caching lai với số bộ đệm tối ưu k, ρ=0,8 Lựa chọn số cache kết hợp mạng kết hợp có thời gian kết nối nhỏ hơn so với kiến trúc phân tầng và thời gian truyền nhỏ hơn kiến trúc phân tán. 3.1.2.3. Thời gian trễ tổng thể Với trường hợp các trang kích thước nhỏ thì số cache kết hợp tối ưu gần với giá trị kc, bởi vì kc tối thiểu thời gian kết nối. Với trường hợp các trang kích thước lớn thì số cache kết hợp tối ưu gần với giá trị kt, bởi vì kt tối thiểu thời gian truyền. Với một kích thước bất kỳ thì số lượng cache kết hợ tối ưu để tối thiểu hóa thời gian trễ có giá trị k opt: kc ≤ k opt ≤ kt 15 k opt phụ thuộc vào kích thước trang, giá trị k opt thay đổi trong khoảng kc =4 và kt=16. Với các trang có kích thước nhỏ hơn hoặc bằng vài KB thì k opt = kc =4 Kiến trúc kết hợp với số cache kết hợp tối ưu có tổng thời gian trễ nhỏ hơn kiến trúc phân tầng và kiến trúc phân tán. 3.1.2.4. Băng thông sử dụng Băng thông sử dụng trong mô hình caching lai nhỏ hơn so với băng thông sử dụng trong mô hình caching phân tán với các mức độ phổ biến khác nhau của nội dung được yêu cầu trong các mạng cấp vùng và cấp quốc gia. Nguyên nhân của kết quả này là do có thêm các máy chủ caching trung gian giúp giảm đáng kể băng thông sử dụng, cũng giống như trong trường hợp sử dung multicast ở lớp ứng dụng. Hiệu năng của mô hình caching lai so với mô hình caching phân cấp phụ thuốc vào số lượng máy chủ caching cộng tác. Đặc biệt trong trường hợp có k = kc = 4 máy chủ caching cộng tác, băng thông sử dụng của mô hình caching lai thậm chí còn nhỏ hơn băng thông sử dụng của mô hình caching phân tán (khoảng 1.2 lần với các văn bản có mức độ phổ biến trung bình). Chú ý rằng, với k = kc = 4, số lượng các chuyển tiếp trung gian của một yêu cầu caching được giảm thiểu. Khi có k = kt = 16 máy chủ caching cộng tác để giảm thiểu thời gian truyền dẫn trong trường hợp mạng nghẽn, băng thông sử dụng tăng nhẹ (khoảng 1.3 lần với các văn bản có độ phổ biến trung bình) so với mô hình thuần phân cấp do sẽ có các trường hợp phải lấy thông tin từ các máy chủ caching ở xa để tránh các đường kết nối bị nghẽn ở mức trên. 3.2. ĐÁNH GIÁ HIỆU NĂNG CÁC THUẬT TOÁN CACHE 3.2.1. Phép thử DEC CE(L) tốt hơn so với các thuật toán thay thế khác theo CRR cho tất cả các kích thước bộ nhớ cache. Các CRR thu được bằng CE là lên tới 140% tốt hơn so với LFU và LRU cho một bộ nhớ cache 10MB. Trong khi tại một bộ nhớ cache 1GB CE(L) thực hiện 23% tốt hơn so với LFU. GDS, cũng xét đến chi phí, kích thước và tuổi cache, đã thực hiện tốt hơn nhiều so LRU và LFU. Nhưng, CE(L) còn thực hiện tốt hơn so với GDS (L) và cải thiện phạm vi tương đối của nó từ 24% đối với bộ nhớ cache nhỏ đến 5% đối với kích thước bộ nhớ cache lớn nhất. CE(P) cũng giảm chi phí tốt hơn LRU, LFU và GDS. Cụ thể, hiệu năng của CE(P) là 67% cao hơn LRU cho một bộ nhớ cache 50MB và cao hơn 50% với bộ nhớ cache 100MB.Hình 3.16 so sánh hiệu năng của các thuật toán về tỷ lệ hit HR. Với kích thước cache vừa phải (200MB và 400MB), CE(P) cải thiện hơn khoảng 50% HR so với LRU và LFU. HR của GDS (P) là tốt hơn một ít so với LRU và LFU. GDS (P) không xem xét tình trạng cache lạnh, do đó hiệu năng của nó cũng không phải là tối ưu.Hình 3.17 so sánh hiệu năng của các thuật toán tỷ lệ byte hit BHR. 16 CE(P) tốt hơn khoảng 10% so với LRU và 20% -30% so với LFU. Tuy nhiên, CE(L) thể hiện hiệu năng hiệu quả ấn tượng về BHR. 3.2.2 Phép thử SJ Phép thử này không tính đến độ trễ tải về cho mỗi yêu cầu, chúng tôi không tính được BV cho CE(L). Vì vậy ở phép thử này chỉ có so sánh hiệu năng của CE(P) với GDS(P), LRU, LFU. Tương tự như các phép thử DEC, CE(P) luôn thực hiện tốt nhất trong việc giảm chi phí lấy được tài liệu. Tuy nhiên, mức độ cải tiến không cao như ở phép thử DEC. Khi kích thước bộ nhớ cache là nhỏ (18MB), CE(P) tốt hơn GDS (P) khoảng 5% và vượt quá LFU khoảng 13%. Về HR và BHR, CE(P) vẫn còn tốt hơn so với các thuật toán thay thế khác như ở phép thử DEC. Lưu ý rằng có hai khác biệt chính giữa 2 phép thử SJ và DEC. Trước tiên, GDS (P) không hiển thị các cải tiến đáng kể trong việc giảm chi phí ở phép thử SJ. Thứ hai, CE(P) có BHR tốt nhất, nhưng việc cải thiện hiệu năng là nhỏ so với những cải tiến trong phép thử DEC. Trong thuật toán CE, một trong những thành phần quan trọng của BV là dự đoán xác suất tái truy cập. Các đối tượng được dự đoán sẽ được truy cập một lần nữa ở lại trong bộ nhớ cache một thời gian dài hơn. Do đó, nếu tải làm việc nhiều truy nhập cục bộ, sẽ có nhiều hit hơn trong cache với thuật toán CE. 3.2.3. Phép thử BO Tương tự như phép thử DEC và SJ, thuật toán CE(P) tốt nhất về CRR và HR. Những ưu thế trên là nhiều hơn đáng kể so với các phép thử trước. Với kích thước bộ nhớ cache 180MB, CE(P) có HR cao hơn 70% so với LRU, 35% so với LFU và 24% so với GDS (P). Hiệu năng cuảng được cải tiến đáng kể cho nhưng kích thước cache khác (xem Hình 3.22). Tuy nhiên, BHR của thuật toán CE(P) không phải luôn luôn là tốt nhất trong phép thử BO (xem Hình 3.23). Đối với các kích thước bộ nhớ cache lớn thì BHR tốt nhất, nhưng với cache nhỏ thì không. Xem xét việc cải tiến hiệu năng của thuật toán CE đối với tỷ lệ giảm chi phí CRR và tỷ lệ hit HR, thì việc BHR giảm nhẹ cho kích thước bộ nhớ cache nhỏ là không đáng kể. 3.2.4.Kết luận Thuật toán CE trong mô hình độ trễ được ký hiệu là CE(L) luôn có tỷ lệ giảm chi phí CRR tốt hơn các thuật toán khác. Thuật toán CE trong mô hình gói được ký hiệu là CE(P) luôn có tỷ lệ hit HR tốt hơn các thuật toán khác. Thuật toán CE(P) đạt được tỷ lệ byte hit (BHR) tốt hơn các thuật toán khá trong trường hợp cache lớn, trong trường hợp cache nhỏ hiệu năng của nó chỉ giảm nhẹ. 17 Chương 4- HIỆN TRẠNG VÀ GIẢI PHÁP TỐI ƯU HỆ THỐNG WEB CACHING MẠNG VNN.VN CỦA VNPT 4.1. HIỆN TRẠNG 4.1.1. Hiện trạng khách hàng và đặc tính lưu lượng Với việc bùng nổ về thuê bao Internet, tính đến tháng 9/2009 đã có hơn 21 triệu người sử dụng Internet, tương đương với tỉ lệ số dân sử dụng Internet 25,6% .Một con số đáng ghi nhận là hiện đã có gần 2,7 triệu khách thuê bao băng thông rộng (xDSL) trên cả nước và hơn 90% doanh nghiệp đã kết nối Internet băng thông rộng. VNPT phấn đấu phát triển 1.000.000 thuê bao truy nhập băng rộng trong năm 2010. Như vậy, với yêu cầu, mục tiêu phát triển các dịch vụ tiềm năng của Công ty năm 2009 và những năm tiếp theo, việc đáp ứng kịp thời các yêu cầu về trang thiết bị phục vụ sản xuất kinh doanh cho mạng VNN là hết sức cấp thiết. Nâng cấp “Hệ thống Caching mạng VNN” thực hiện mục tiêu nâng cao chất lượng dịch vụ Internet trên cơ sở đáp ứng nhanh hơn các yêu cầu truy cập. Đặc tính lưu lượng mạng VNN là tập trung nhiều nhất ở khu vực HNI và HCM. Lưu lượng dành cho khách hàng băng rộng cũng được đổ dồn từ các node mạng trục về các BRAS chính ở tầng mạng truy nhập – nơi tiếp yêu cầu từ phía khách hàng là rất lớn. 4.1.2. Hiện trạng hệ thống Web Caching mạng VNN.VN Hình 4.2. Sơ đồ tổng quan kiến trúc Web Caching hiện tại của VNPT VNPT hiện nay đang sử dụng hệ thống Web Caching cho tầng mạng trục (core network) của mạng VNN. 18 4.1.3. Hiện trạng lưu lượng các hướng trên mạng VNN Hệ thống Web Caching hiện nay của VNPT làm giảm thiểu đáng kể lưu lượng mạng từ mức vùng lên mức quốc gia và giảm nghẽn nút cổ chai ở các nút trung tâm vùng. Tuy nhiên, không tối ưu lưu lượng theo từng địa phương có tỉ lệ mật độ dân cư, dân trí, mức sống khác nhau. Do đó, đối với những truy nhập ở các địa phương có nhu cầu sử dụng thấp thì không hiệu quả, còn những nơi có nhu cầu cau như thành phố Hồ Chí Minh, Hà Nội, Hưng Yên... thì hiệu quả đem lại thấp. Cũng vì vậy chất lượng dịch vụ ở các nơi này chưa được cao và còn chưa thỏa mãn đòi hỏi của người sử dụng đặc biệt là trong những thời gian cao điểm (dịp lễ, tết...). Vẫn còn hiện trang lưu lượng sử dụng trên 80% dung lượng băng thông. Như vậy, yêu cầu đặt ra là cần phải có giải pháp nâng cấp tôí ưu hệ thống Web Caching, tiết kiệm chi phí bằng thông hơn. 4.1.4. Đánh giá và nhận định hiện trạng *. Ưu điểm: - Hệ thống sử dụng cache farm cho cả ba khu vực, nó sẽ giảm chi phí mạng do nhiều yêu cầu sẽ được thỏa mãn với những dữ liệu lưu trữ bên trong cache farm, giảm thời gian truyền dẫn, tiết kiệm chi phí trên đường truyền mạng - Trong mỗi cache farm bao gồm những Content Engine của Cisco nên nó mang đầy đủ đặc tính kĩ thuật của Cache Engine. - Qua theo dõi hoạt động, hệ thống Web Caching mạng VNN đã góp phần giảm một phần đáng kể dung lượng kênh Internet quốc tế bằng việc hoạt động hiệu quả, tỷ lệ tiết kiệm bằng thông thường xuyên đạt 25-30% của tổng lưu lượng HTTP trên mạng. - Hệ thống Web Caching đã chứng tỏ được hiệu quả về mặt kỹ thuật và tính kinh tế so với việc mở kênh Ineternet quốc tế trực tiếp mà không sử dụng hệ thống Caching. - Ngoài ra, hệ thống Web Caching còn có vai trò quan trọng trong việc ngăn chặn các truy cập tới các địa chỉ web đen từ phía người sử dụng nhằm đảm bảo an toàn thông tin, hạn chế việc quảng bá các nội dung “bẩn” vào Việt Nam qua mạng Internet toàn cầu. - Web Caching cũng hỗ trợ tốt tính năng xác thực truy nhập người dùng nhằm đáp ứng yêu cầu đặc thù trong việc quản lý nội dung trên Internet của các cơ quan quản lý nhà nước. Việc thực hiện chức năng này trên hệ thống caching cũng làm giảm tải hệ thống firewall hoặc không cần dùng đến hệ thống firewall nữa tạo thuận lợi cho hệ thống mạng được thông suốt hoàn toàn, hạn chế việc hình thành các nghẽn nút cổ chai trên mạng do sử dụng các hệ thống firewall trên mạng. *. Nhược điểm: - Hiện nay hệ thống Web Caching mới chỉ được sử dụng ở tầng mạng trục mạng VNN, các tầng mạng khác chưa có Web cache. 19 - Mạng VNN sử dụng kiến trúc Web Caching phân tán tại mức vùng, nó sẽ giảm lưu lượng mạng từ mức vùng lên mức cao hơn (mức quốc gia) nhưng trong kiến trúc mạng VNN ta nhận thấy tại mức quốc gia và mức khu vực (các tỉnh, điểm tập trung lưu lượng của các POPs) chưa có caching. Vì vậy nó sẽ dẫn đến tình trạng “nghẽn nút cổ chai” trên đường truyền từ các điểm tập trung lưu lượng của các POPs đến khu vực và nghẽn từ miền đến mức cao hơn khi số lượng người truy nhập tăng lên (ví dụ trong những ngày lễ tết, trong những giờ cao điểm số lượng người truy nhập tăng cao). - Các thiết bị trong hệ thống Web caching chỉ sử dụng thuật toán LRU, làm lãng phí dung lượng bộ nhớ của cache để lưu các trang multimedia có kích thước lớn mà dường như sẽ không được truy nhập lại trong thời gian trước mắt, do đó chỉ đạt hiệu năng cao với truy nhập cục bộ các đối tượng cùng kích thước và cùng chi phí - Lưu lượng đi ra từ tầng mạng trục xuống tới các điểm tập trung lưu lượng (các BRAS) của các POPs (tỉnh) trọng điểm (nơi tiếp nhận các yêu cầu từ khách hàng là rất lớn. Vì vậy tại thời kỳ cao điểm có thể gây nghẽn nút cổ chai do yêu cầu từ phía khách hàng tăng cao. - Thực tế hệ thống Web Caching mạng VNN hiện tại mới chỉ đảm bảo phục vụ cho một bộ phận khách hàng băng rộng, chưa đảm bảo phục vụ cho toàn bộ khách hàng băng rộng cũng như khách hàng các loại. - Hệ thống bị quá tải nên thỉnh thoảng việc vận hành khai thác phải tiến hành reset lại bằng tay để giải phóng tài nguyên, hệ thống đã làm mất các nội dung được lưu trữ trên Cache và làm cho Cache phải đi lấy nội dung lại từ đầu, việc tiết kiệm băng thông đi quốc tế bị giảm đáng kể. Qua các phân tích trên ta thấy: Hệ thống Web Caching mạng VNN hiện dùng chưa tương xứng với quy mô khách hàng (lưu lượng) phát triển trên mạng. Tầng mạng truy nhập ở các POP nơi tập trung nhiều truy nhập ở các tỉnh khác nhau có lưu lượng khác nhau, do đó sự đầu tư web caching cho tầng POP khu vực có thể đem lại hiệu quả sử dụng kênh truy nhập lên tầng mạng trên tốt hơn nhưng hiện nay VNPT chưa đầu tư Web Caching ở các POPs (Web Proxy server). 4.2. GIẢI PHÁP NÂNG CẤP WEB CACHING CHO MẠNG VNN 4.2.1. Giải pháp - Hệ thống sẽ sử dụng kiến trúc kết hợp (kiến trúc lai), bao gồm nhiều cấp caching và nhiều thành phần caching trong mỗi cấp. - Ở chương 3 chúng ta đã đánh giá hiệu năng của các thuật toán thay thế cache LRU, LFU, GDS, CE bằng thực nghiệm. Kết quả quan sát cho thấy CE gần như luôn đạt được tỷ lệ hit, tỷ lệ byte hit, tỉ lệ giảm chi phí tốt nhất. Vì vậy việc sử dụng thuật toán CE là lựa chọn tối ưu hiện thời. 20 - Thiết bị được chọn sử dụng trong hệ thống Web Caching là Cisco Cache Engine. - Dựa vào bảng thống kê lưu lượng ở trên, để giải quyết vấn đề giảm nghẽn cổ chai tại các POPs có lưu lượng cao. Trong giai đoạn đầu nâng cấp hệ thống Web Caching mới chúng tôi đưa ra phương án: Đầu tư Cache farm cho các điểm tập trung lưu lượng lớn tại các tỉnh Hà Nội, Hồ Chí Minh, HYN, HDG nhằm san tải nhanh chóng khi lượng yêu cầu của khách hàng tăng cao. - Sử dụng thêm Web Caching P2P (Caching ngang hàng hay web caching tại mức quốc gia với các nhà cũng cấp dịch vụ khác) nhằm giảm lưu lượng mạng đi quốc tế. 4.2.2. Sơ đồ kiến trúc giải pháp Web Caching cho mạng VNN.VN Hình 4.4. Sơ đồ tổng quan giải pháp Web Caching cho mạng VNN của VNPT Hình 4.5. Sơ đồ chi tiết Web caching tại POP HYN