Evaluating caching schemes for the X.500 directory system

The OSI directory system is a distributed directory information database which incorporates distributed algorithms for name resolution and search to support applications such as electronic mail, White Pages, authentication services, etc. To improve the performance of requests for name resolution and search, it is necessary to lower the cost of name lookups for nonlocal names. The OSI directory system and other distributed naming systems use name caching to minimize such costs. In this paper, we evaluate the impact of name caching on the performance of the OSI directory system. We consider the issues of cache sizing and cache replacement policies. We find that a locality of reference property holds in name resolution requests, and hence name caching does increase performance significantly. Using trace-driven simulation, we show that small caches (smaller than 30 items) yield hit ratios up to 60% and decrease the average name resolution time by 60%. For small caches, the LRU (Least Recently Used) replacement policy is better than other implementable policies. Large caches yield predictably larger hit ratios. For large caches, however, the LRU policy is not better than a random replacement policy. We also find that partitioning the cache buffer into a small number of independent caches, each one associated with a different kind of name requests, further decreases the average name resolution time.