Steiner-optimal data replication in tree networks with storage costs

摘要

We consider the problem of placing copies of objects at multiple locations in a distributed system, whose interconnection network is a tree, in order to minimize the cost of servicing read and write requests to the objects. We assume that the tree nodes have limited storage and the number of copies permitted may be limited. The set of nodes that have a copy of the object, called replica nodes, constitute the replica set of the object. Read requests of a node are serviced from the closest replica node. Write requests of a node are propagated to all the replicas of the object using a minimum cost Steiner tree that includes the writer and all replica nodes. The total cost associated with a replica set equals the cost of servicing all the read and write requests, plus the storage cost at all the replica nodes. We are interested in finding a replica set with minimum total cost, i.e. a Steiner-optimal replica set. Given a tree with n nodes, we provide an O(n/sup 6/p/sup 2/)-time algorithm for finding a Steiner-optimal replica set of size p, taking into consideration the read, write, and storage costs. Our algorithm can also find a Steiner-optimal replica set for a tree with n nodes in time O(n/sup 8/). We also demonstrate that the policy used to propagate write requests to all the replica nodes in the network affects the cost and configuration of the optimal replica set for the object.