| As the rapid expansion of the World Wide Web continues, the development of the internet infrastructure cannot sustain demand. Caching systems, as widely employed in various network systems, reduce delays in terms of both information processing and communication bandwidth requirements.; Caching systems are mostly used in access level routers and web proxies/servers. The purpose of router caching is to improve the packet forwarding performance in a router whereas web caching is to improve the performance of the network. Both systems need to achieve high utilization to boost the system performance. The subject of this dissertation is to propose novel and improved models to achieve high caching utilization.; For caching in routers, we analyzed flow caching mechanisms for fast packet forwarding. We demonstrated through model analysis that flow caching performance is not sensitive to cache table lookup speed while it is sensitive to cache hit ratio. Taking advantage of the available layer-4 information, we introduce two filtering modules to reduce the cache miss ratio.; In addition, we demonstrated using real trace simulation, that by adding the two newly-introduced filtering modules, the cache miss ratio can be decreased by as much as 50%. The conventional requirement for full header filtering speed can also been greatly reduced by employing our proposed system of modules.; For web proxies/servers, our initial approach is to focus on hierarchical web caching. By proposing a stochastic model, we were able to characterize the caching process for individual documents in a two-level hierarchical caching system. Using our model, the least recent used (LRU) algorithm runs at individual caches in an uncooperative manner. We used a mean field approximation to solve this model. We were able to pinpoint a characteristic time associated with each cache and find out two design principles for hierarchical web caching systems. Based on these principles, we developed a cooperative hierarchical caching architecture. To test our cooperative caching architecture, we generated simulations using both models and real traces. We show conclusively that our proposed cooperative architecture provides 50% cache resource saving as compared to the traditional uncooperative hierarchical caching architecture.; We proceeded to introduce our design principle associated with the characteristic time in the design of two algorithms in distributed web caching. Based on the real trace simulation, we were able to confirm that both latency and cache miss ratio are greatly reduced. Furthermore, we also show by simulation studies that the characteristic time we found is relatively stable and do not need to be upgraded frequently. |
