Analysis of a class of distributed directory algorithms

Abstract

In this paper, we analyze a class of distributed algorithms for performing the directory function in a network. The directory function involves resolving a resource name to the address of the network node at which it resides. The simplest directory scheme consists of nodes maintaining information about only their own resources, and performing a network-wide search to locate other resources. An obvious extension of this scheme is to provide additional storage or cache at the network nodes to store the results of a previous query for a remote resource, so that a subsequent query for that resource can be resolved locally. We refer to this as the local cache (LC) scheme. We investigate two enhancements of this basic scheme. The first is the regional cache server (RCS) scheme where queries not resolved locally are forwarded to a regional "server" node. Since all nodes in a region forward their queries to the same server, multiple network-wide searches for a given resource are avoided in the region. The servers operate independently of other regional servers. The second scheme is called the cooperating cache servers (CCS) scheme. Here the regional servers cooperate to resolve a query before resorting to a network-wide search. The performance of these schemes in terms of the frequency of network-wide search to locate resources depends on the cache sizes at the nodes and servers, the probability distribution for querying different resources and the cache replacement policy used to displace resources from the cache to accommodate newly discovered ones. The analysis presented in the paper follows the analysis of cache replacement policies for demand paging in computer systems. In particular, we investigate two policies - A 0, which is the optimal policy for the LC scheme, and Least Recently Used policy, which is of practical importance. We extend the LC analysis to the RCS and CCS schemes. We also show that the limiting network search rate attains its maximum when the query distributions at the nodes and the servers are uniform distributions. We illustrate the results via numerical examples. © 1989 IEEE.