File allocation involving worst case response times and link capacities: Model and solution procedure

A major design issue facing the designer of a distributed computing system involves the determination of the number of file copies and their locations in the distributed environment. This problem is commonly referred to as the file allocation problem (FAP). In this paper, a FAP model is formulated that seeks to obtain the lowest cost file allocation strategy, that ensures the attainment of acceptable levels of response times during peak demand periods, for all on-line queries. Unlike previous FAP research, the proposed model treats response time on a query-by-query basis, and not as a single, system wide average delay constraint. A Lagrangian relaxation based solution procedure is proposed for the resulting 0/1 integer programming problem. Results of computational experiments with the proposed solution procedure are reported.